WuWei - Functional Mutability

Relies onLambda.

This library includes theSTmonad along withSTRefs to provide delimited scopes for safe mutations in Java.

Unlike theIOmonad:

1. There is an expectation for a clear start and finish to mutations within theSTmonad. Once complete, the resulting value is frozen and can be used safely as an immutable object.
2. The sole effect within anSTmonad is the mutation of a provided object. The addition of other sorts ofIOeffects (database work, logging statements, etc.) is considered a breach of contract and may be dropped in optimizations.

Examples

Using normal monadic composition:

Integerres=STRef.<Integer>stRefCreator()
.createSTRef(-10)
.flatMap(ref->ref.writeSTRef(1))
.flatMap(ref->ref.modifySTRef(value->value*2))
.flatMap(ref->ref.readSTRef)
.runST();
assertThat(res,equalTo(2));

Abstracting out effects:

STRefModifier<Integer>set=writer(1);
STRefModifier<Integer>inc=modifier(value->value*2);
STRefModifier<Integer>setAndInc=set.and(inc);

Integerres=STRef.<Integer>stRefCreator()
.createSTRef(-10)
.flatMap(setAndInc.run())
.flatMap(STRef::readSTRef)
.runST();
assertThat(res,equalTo(2));

STRef Usage

The purpose of anSTRefis that all of its actions take place in theSTmonad. This involves passing an internal type parameter through the chain of operations. If at any point one attempts to break the chain of operations and release a mutableSTRefinto the wild, type inference will break. One must:

1. Create an STRef
2. Perform the operations on an STRef
3. Read the STRef
4. And, finally, runST to release the read value from theSTmonad.

Creating and Running an STRef

In order to create an STRef, use an stRefCreator:

ST<?,?extendsSTRef<?,Integer>>stRef=STRef.<Integer>stRefCreator()
.createSTRef(0);

Because of the type captures, this variable stRef is unusable in any further operations - the type inference engine would need to unify both the capture inSTand inSTRefand verify they are the same, which it can't do. To resolve this, read theSTRef:

ST<?,Integer>stResult=STRef.<Integer>stRefCreator()
.createSTRef(10)
.flatMap(STRef::readSTRef);

At which point the result no longer would leak an STRef, and can be run:

Integerten=integerST.runST();

Performing operations with flatmaps

The two operations that be used to mutate anSTRefareSTRef#writeSTRefandSTRef#modifySTRef:

IntegerwrittenAndModified=STRef.<Integer>stRefCreator()
.createSTRef(10)
.flatMap(stRef->stRef.writeSTRef(0))
.flatMap(stRef->stRef.modifySTRef(x->x+1))
.flatMap(STRef::readSTRef)
.runST();

STRef#writeSTRefwill replace the reference value.STRef#modifySTRefwill modify the reference value in place using the provided function.

Performing operations with STRefModifier

As stated above, a chain of actions on anSTRefcannot be abstracted out, as it would leak theSTRefand fail type checking. In order to create compositional units of work onSTRefs,one can use anSTRefModifierinstead. To create a write action, useSTRefModifier#writer:

STRefModifier<Integer>writeTen=writer(10);

And to modify,STRefModifier#modifier:

STRefModifier<Integer>triple=modifier(x->x*3);

These can be combined:

STRefModifier<Integer>writeTenThenTriple=writeTen.and(triple);

Since the only two mutable actions allowed for anSTRefare writing and modification, and writing will overwrite whatever is currently in the reference whatever it is,STRefModifierfeatures an optimization where awritewill wipe the slate clean and start from scratch, no matter how many other actions have beenaddedbefore it. So the following:

STRefModifier<Integer>tripleThenWriteTen=triple.and(writeTen);

is the same aswriteTenon its own.

Performance

For lightweight types, regular lambda functions will work fine, if not better. For example, thisSTRefsummation algorithm:

Integerinteger=STRef.<Integer>stRefCreator()
.createSTRef(0)
.flatMap(s->s.modifySTRef(trampoline(a->a>1_000_000?terminate(a):recurse(a+1))))
.flatMap(STRef::readSTRef)
.runST();

runs at about the same speed as the simpler:

Integerinteger=foldLeft((acc,n) ->acc+n,0,replicate(1_000_000,1));

and takes significantly longer if the trampolining is done in-place in a monadic context (~10x the time).

However, for heavier-weight objects, theSTRefimplementation is significantly faster. For example, using the following class:

publicstaticclassFoo{
privatefinalIterable<Integer>m;
privateintn;

publicFoo(Iterable<Integer>m,intn) {
this.m=m;
this.n=n;
}

publicFooincImmutable() {
returnnewFoo(m,n+foldLeft(Integer::sum,0,m));
}

publicFooincMutable() {
this.n+=foldLeft(Integer::sum,0,m);
returnthis;
}
}

the followingSTRefimplementation with a mutable object runs locally at about 180 - 200ms for a lazy collection and 20-25ms for a strict collection, after JVM optimizations:

FoofooLazy=STRef.<Foo>stRefCreator()
.createSTRef(newFoo(take(10,iterate(n->n+1,1)),0))
.flatMap(s->s.modifySTRef(trampoline(f->f.n>10_000_000?terminate(f):recurse(f.incMutable()))))
.flatMap(STRef::readSTRef)
.runST();

ArrayList<Integer>m=toCollection(ArrayList::new,take(10,iterate(n->n+1,1));
FoofooStrict=STRef.<Foo>stRefCreator()
.createSTRef(newFoo(m,0))
.flatMap(s->s.modifySTRef(trampoline(f->f.n>10_000_000?terminate(f):recurse(f.incMutable()))))
.flatMap(STRef::readSTRef)
.runST();

while thefoldLeftimplementation with immutable objects runs around 13000 - 15000ms for a lazily-constructed Iterable,and 1300 - 1500ms if theIterableis forced into anArrayList:

FoofooLazy=foldLeft((acc,n) ->acc.incImmutable(),
newFoo(take(10,iterate(n->n+1,1)),0),
replicate(10_000_000,1));

ArrayList<Integer>m=toCollection(ArrayList::new,take(10,iterate(n->n+1,1));
FoofooStrict=foldLeft((acc,n) ->acc.incImmutable(),
newFoo(m,0),
replicate(10_000_000,1));