This is about continuations, really.
This is the continuing series of articles of continuing on continuations. Really.
And State. Oh, and State. Ugh.
So, the State monad is a monad on a 'stateful-like' function.
Still with me?
So I have this beautiful implementation in Java — No, really. I do. — and, so ... how do I test that it works?
Well, you know I have to use it. I have this State monad transformer example, but I want something really, really simple, so:
> inc :: State Int Int
> inc = do x <- get
> put (x + 1)
> return x
But the thing is, we don't have the do-notation in Java, so we have to unwind this as a set of monadic binds, so:
> inc1 = get >>= \x -> put (x + 1) >> return x
Cool! But we don't have (>>) ('then') in Java, we have (>>=) ('bind'), so one more transformation:
> inc2 = get >>= \x -> put (x + 1) >>= \_ -> return x
AND we're done! Now, an example:
> runState (inc2 >> inc2 >> inc2) 2
and we get:
(4, 5)
as expected.
Shoot, do we have to write (>>) ('then') as a convenience function? We still have to take the argument and declare the type of the function, but the function itself simplifies. Let's see the Java implementation first as:
> runState (inc2 >>= \_ -> inc2 >>= \_ -> inc2) 2
(still works...)
So, State is a straight transliteration from Haskell to Java. It's a monad of a function:
public class State<STATE, DATUM> implements Monad<State, DATUM> {
protected State(Arrow<STATE, Tuple<DATUM, STATE>> f) {
state = f;
}
// get and put are straight from the haskell standard library:
// get = State $ \x -> (x, x)
// so is x <- get the same as get >>= State $ \state -> (x, state1)
public static <STATE1> State<STATE1, STATE1> get(STATE1 basis) {
return new State<STATE1, STATE1>(Tuple.dupF(basis));
}
// put :: a -> State a ()
public static <STATE1> State<STATE1, Unit> put(final STATE1 s) {
Arrow<STATE1, Tuple<Unit, STATE1>> putter =
new Function<STATE1, Tuple<Unit, STATE1>>() {
public Tuple<Unit, STATE1> apply(STATE1 ignored) throws Failure {
return Tuple.pair(Unit.instance, s);
}
};
return new State<STATE1, Unit>(putter);
}
// eval/exec/run State functions are yawn-worthy:
public DATUM evalState(STATE s) throws Failure {
return state.apply(s).fst();
}
public STATE execState(STATE s) throws Failure {
return state.apply(s).snd();
}
public Tuple<DATUM, STATE> runState(STATE s) throws Failure {
return state.apply(s);
}
// now here comes the fun stuff. Functor:
// Functor override --------------------
/*
instance Functor (State s) where
fmap f m = State $ \s -> let
(a, s') = runState m s
in (f a, s')
*/
public <A, B> Arrow<Functor<A>, Functor<B>> fmap(final Arrow<A, B> fn) {
return new Function<Functor<A>, Functor<B>>() {
public Functor<B> apply(final Functor<A> functor) throws Failure {
// TODO: implement -- uh, fmap and >>= are the same for state
// ... almost
Arrow<STATE, Tuple<B, STATE>> stater =
new Function<STATE, Tuple<B, STATE>>() {
public Tuple<B, STATE> apply(STATE s) throws Failure {
State<STATE, A> m = (State<STATE, A>)functor;
final Tuple<A, STATE> tup = m.runState(s);
return Tuple.pair(fn.apply(tup.fst()), tup.snd());
}
};
return new State<STATE, B>(stater);
}
};
}
// and monad bind and return and then:
// Monad overrides ---------------------
public <X> Monad<State, X> unit(final X d) {
Arrow<STATE, Tuple<X, STATE>> lifter =
new Function<STATE, Tuple<X, STATE>>() {
public Tuple<X, STATE> apply(STATE st) throws Failure {
return Tuple.pair(d, st);
}
};
return new State<STATE, X>(lifter);
}
// state >>= f = State $ \st ->
// let (x, st') = runState state st
// in runState (f x) st'
public <B> Monad<State, B> bind(final Arrow<DATUM, Monad<State, B>> fn)
throws Failure {
final State<STATE, DATUM> status = this;
Arrow<STATE, Tuple<B, STATE>> binder =
new Function<STATE, Tuple<B, STATE>>() {
public Tuple<B, STATE> apply(STATE st) throws Failure {
Tuple<DATUM, STATE> tup = status.runState(st);
return ((State<STATE, B>)fn.apply(tup.fst()))
.runState(tup.snd());
}
};
return new State<STATE, B>(binder);
}
// join() ???
public Monad<State, ?> join() throws Failure {
throw new Failure("Okay, why are you joining on state?");
}
public <A, B> Arrow<A, Monad<State, B>> liftM(Arrow<A, B> fn) {
return Monad.Binder.lifter(this, fn);
}
public <B> Monad<State, B> liftThenBind(Arrow<DATUM, B> fn)
throws Failure {
return bind(liftM(fn));
}
public <T> Monad<State, T> then(final Monad<State, T> m) throws Failure {
return bind(new Function<DATUM, Monad<State, T>>() {
public Monad<State, T> apply(DATUM ignored) throws Failure {
return m;
}
});
}
// just capture types here -----
private final Arrow<STATE, Tuple<DATUM, STATE>> state;
}
... and with that we have (functional) state!
Now, to test it with our inc2 function(al):
// So we need to test the hell out of this ...
public static void main(String args[]) throws Failure {
// TODO: test me! well a simple test is monadic succ, so ...
// inc2 :: State Int Int
// inc2 = get >>= \x -> put (x + 1) >> return x
Monad<State, Integer> inc2 =
State.get(0).bind(new Function<Integer, Monad<State, Integer>>() {
public Monad<State, Integer> apply(final Integer x)
throws Failure {
return State.put(x + 1)
.then(new State<Integer, Integer>(
Tuple.mkWithFst(x, 0)));
}
});
System.out.println("runState (inc2 >> inc2 >> inc2) 2 is (4,5): "
+ ((State<Integer, Integer>)
(inc2.then(inc2).then(inc2))).runState(2));
System.out.println("runState (inc2 >> inc2 >> inc2) 17 is (19, 20): "
+ ((State<Integer, Integer>)
(inc2.then(inc2).then(inc2))).runState(17));
}
And the results output are as expected. YAY!
You see that I did implement the (>>) ('then') operator in Java. It was very easy to do: just a bind-ignore-return.
Now.
Now.
Now. (Now, I'm going to stop saying 'now.' Really.)
Now that we have state, we can use it along with continuations to create a threading or coroutining model of computation without having to use the (dreaded/revered) call/cc.2
Tune in next week, Ladies and Gentlemen, for another thrilling chapter on our continuing saga of continuations!
-----
(2) "Oh, you code with call/cc?" the awed neophyte whispers reverentially, then bows down and worships.3
(3) Thus spake the Zen Master: "Why are you in awe of those who use call/cc and similar parlor tricks? The real miracle is that when I wish to sum, I use (+), and when I wish to 'continue' I hit the carriage return." Then he concluded his lesson with the cryptic utterance: "One bowl of rice" and departed their presence for Nirvana (he likes Soundgarden, as well).
Chapter Postlude
The problem that this chapter addresses is what I've had in my java categories library for some time now. I've had this thing called 'MutableBoxedType<T>' with a very easy implementation:
@Effectual public class MutableBoxedType<T>
implements Functor<T>, Copointed<T> {
public MutableBoxedType(T val) {
this.value = val;
}
@Effectual public void put(T newval) {
this.value = newval;
}
@Effectual public final Effect<T> putF = new Effect<T>() {
@Override protected void execute(T obj) throws Failure {
put(obj);
}
};
// Functor implementation -----------------------------------
public <X, Y> Arrow<Functor<X>, Functor<Y>>
fmap(final Arrow<X, Y> fn) {
return new Function<Functor<X>, Functor<Y>>() {
public Functor<Y> apply(Functor<X> obj)
throws Failure {
MutableBoxedType<X> mbt =
(MutableBoxedType<X>)obj;
return new MutableBoxedType<Y>(fn.apply(mbt.extract()));
}
};
}
// Copointed implementation --------------------------------
public T extract() {
return value;
}
private T value;
}
Simple enough, we just put a box around a mutable type. The problem is all those @Effectual annotations and the very mutability-ness of the type itself. Once we make the guts of an instance mutable we lose all provability as 'equals' and '==' now have been reduced to meaningless, vis:
MutableBoxedType<Integer> five = new MutableBoxedType<Integer>(5);
oldFive= five;
five.put(12);
five.equals(oldFive); ... is true
Yes, five and oldFive are equal, but their shapes have changed during the course of the program and we need deep copy semantics here to sniff that out.
The (functional) state monad doesn't 'change' ... not via mutation, anyway. What happens instead is that when the state gets updated, we have a new state. It just makes sense (provably so) and gives us our beloved 'mutation' (by all appearances) even in the functional domain.
