So, okay, we've shown how to lift continuation functions up into the monadic domain, so we could control the input to a continuation, just as we've shown how we can (very easily) control the output from such a function.
And the '(very easily)' is the rub there. If it's the output of the function that concerns us,1 then let's simply work with the output, good or bad.
There's a pattern that addresses this, it's known as the Either data type:
> data Either a b = Left a | Right b
The Either type, itself, is not a functor, as it represents choice. By convention this falls very nicely into failure conditions where we wish to know what went wrong:
> type Answer a = Either a String
If we get back a Left a solution, we know our answer is good; but if we get back a Right String answer, then we know we had an error, and the error message is contained in the string. We can use the either function to dispatch on our called-function's output:
> either :: (a -> c) -> (b -> c) -> Either a b -> c
So, all that heavy lifting of CPS-functions we did in the last chapter to make them monadic ...?
Let's return to the drawing board, restarting from the example code base where we made our divBy function in the CPS-style for unit values:
public ANS appDivBy(final Arrow<Integer, ANS> tail, Integer by)
throws Failure {
return Continuity.divBy(basis).apply(by)
.apply(new Function<Integer, ANS>() {
public ANS apply(Integer x) throws Failure {
return app(tail, basis, x);
}
});
}
And with the Either type ...
Whoopsie, we need to define our Either type in Java, first, before we can use it! Java is particular about these kinds of things.
Funny, that.
Well, the type is very easy to declare:
interface Either<LEFT, RIGHT> {
public <ANSWER> ANSWER
either(Arrow<LEFT, ANSWER> afn, Arrow<RIGHT, ANSWER> bfn)
throws Failure;
}
The Either type gives us the data structure of choice (materializing that choice, once it's made), and the function that dispatches on that choice.
I'd give you the implementation for Left and Right, the two materialized options of the Either choice, but we have to do a bit of ground-work to make them happen. Or should I just try to develop the two subtypes of Either and let the basic types fall out, as what happened when I did the development work? Yes, let's do that.
First, let's define our Right option of our Either choice-point:
public class Right<LEFT, RIGHT>
implements Functor<RIGHT>, Either<LEFT, RIGHT> {
public Right(Right value) {
this.arg = value;
}
// Functor implementation -----------------------
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(Functor<A> func) throws Failure {
Right<?, B> ans = null;
try {
Right<?, A> righto = (Right<?, A>) func;
ans = new Right<?, B>(fn.apply(righto.arg()));
} catch(Exception ex) {
throw new Failure("Unable to fmap(Right) for " + func);
}
return ans;
}
};
}
public Right arg() { return arg; }
// Either implementation -------------------
public <ANSWER> ANSWER
either(Arrow<LEFT, ANSWER> a, Arrow<RIGHT, ANSWER> b)
throws Failure {
return b.apply(arg());
}
// Object override ----------------
@Override public String toString() {
return getClass().getSimpleName() + "<" + arg() + ">";
}
private final RIGHT arg;
}
So, then we have the 'left' option of an Either choice point:
public class Left<LEFT, RIGHT>
implements Functor<LEFT>, Either<LEFT, RIGHT> {
public Left(LEFT value) {
this.arg = value;
}
// Functor implementation -----------------------
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(Functor<A> func) throws Failure {
Left<B, ?> ans = null;
try {
Left<A, ?> louie = (Left<A, ?>) func;
ans = new Left<B, ?>(fn.apply(louie.arg()));
} catch(Exception ex) {
throw new Failure("Unable to fmap(Left) for " + func);
}
return ans;
}
};
}
public LEFT arg() { return arg; }
// Either implementation -------------------
public <ANSWER> ANSWER
either(Arrow<LEFT, ANSWER> a, Arrow<RIGHT, ANSWER> b)
throws Failure {
return a.apply(arg());
}
// Object override ----------------
@Override public String toString() {
return getClass().getSimpleName() + "<" + arg() + ">";
}
private final LEFT arg;
}
There's a lot of red in the above code. Why? Well, because we already implemented all that code in the Right<?, RIGHT> type. All the red code is repeated, nearly verbatim, just replacing 'Left's for 'Right's. What's going on here? It seems like there's shared functionality here.
There is.
The thing is, are functors require to carry around some unit type? I argue: no. The intrinsic property of a functor is that it is mappable from one category to the other: fmap(). I further argue that it is not intrinsic to a functor-type to carry a value. So I said arg() is not part of the Functor protocol.2
And this, by definition, fits in very nicely with the whole concept of monads. Once you're lifted into the monadic domain, you stay there, and you are not allowed to extract() values from the monad. For example: try extracting a value from Maybe.NOTHING, or from [] ... you get an error. I argue even more strongly than this arg() against a(n unspecified) monad should not compile!
And that's my heart-ache with the above code. Left, by declaration, is a Functor, but it shouldn't have to carry around all these marshalling and unmarshalling functions around a carried type. A generic type-carrying type should have all that functionality and Left and Right should shunt or delegate all this functionality to that type-carrying type.
What could this type be?
Well, the obvious candidate is Id.
public class Id<T> implements Functor<T> {
public Id(T val) {
arg = val;
}
public T arg() { return arg; }
// Functor override --------------------------
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(Functor<A> func) throws Failure {
Id<B> ans = null;
try {
Id<A> id = (Id<A>) func;
ans = constructor(fn.apply(id.arg()));
} catch(Exception ex) {
throw new Failure("Unable to fmap(id) for " + func);
}
return ans;
}
};
}
protected <X> Id<X> constructor(X val) {
return new Id<X>(val);
}
// Object overrides --------------------------
@Override public String toString() {
return getClass().getSimpleName() + "<" + arg() + ">";
}
@Override public int hashCode() {
int hash = getClass().hashCode();
if(arg() != null) {
hash += 7 * arg().hashCode();
}
return hash;
}
@Override public boolean equals(Object obj) {
if(obj instanceof Id) {
Id id = (Id)obj;
if(arg() == null) return id.arg() == null;
return arg().equals(id.arg());
}
return false;
}
private final T arg;
}
With this common class as a parent, both in functionality and in type-inheritance (both Left and Right are identifying types or type labels on the underlying values), both Left and Right reduce to much smaller implementations:
public class Left<LEFT, RIGHT> extends Id<LEFT>
implements Either<LEFT, RIGHT> {
public Left(LEFT value) {
super(value);
}
// Id override -----------------------
protected <X> Id<X> constructor(X val) {
return new Left<X, Unit>(val);
}
// Either override -------------------
public <ANSWER> ANSWER
either(Arrow<LEFT, ANSWER> a, Arrow<RIGHT, ANSWER> b)
throws Failure {
return a.apply(arg());
}
}
and for Right:
public class Right<LEFT, RIGHT> extends Id<RIGHT>
implements Either<LEFT, RIGHT> {
public Right(RIGHT value) {
super(value);
}
// Id override -----------------------
protected <X> Id<X> constructor(X val) {
return new Right<Unit, X>(val);
}
// Either override -------------------
public <ANSWER> ANSWER
either(Arrow<LEFT, ANSWER> a, Arrow<RIGHT, ANSWER> b)
throws Failure {
return b.apply(arg());
}
}
Much, much simpler!
You see in these implementations the constructor() function supplies our (sub-)type, so that fmap() on Id works equally well for these types, as well.
You also saw in the original implementation the following (questionable) type: ? That type has been replaced by the Unit type (familiar to you Haskell-functional programmers). Unit is what? One? Well, yes, there's only one Unit instance, because it represents the null or nothing value in the unit category:
public class Unit {
private Unit() { }
@Override public String toString() { return "()"; }
public static final Unit instance = new Unit();
}
Easy, peasy!
And, in fact, with just these elements, we have a system sufficient to handle normal and erroneous states (or any left or right paths) for our simple arithmetic system:
class ResultE extends Result<Either<Integer, String>> {
public ResultE(Either<Integer, String> res) {
super(res);
}
public Either<Integer, String>
apply(final Arrow<Integer, Either<Integer, String>> tail)
throws Failure {
return appE(tail, basis, 3);
}
private static Either<Integer, String>
appE(final Arrow<Integer, Either<Integer, String>> tail,
final Either<Integer, String> basis, Integer in) throws Failure {
return Continuity.g(basis).apply(in)
.apply(new Function<Integer, Either<Integer, String>>() {
public Either<Integer, String> apply(Integer x) throws Failure {
return Continuity.f(basis).apply(x).apply(tail);
}
});
}
public Either<Integer, String>
appEDivBy(final Arrow<Integer, Either<Integer, String>> tail,
Integer by)
throws Failure {
Either<Integer, String> ans = null;
try {
Continuation<Integer, Either<Integer, String>> cont =
Continuity.divBy(basis).apply(by);
ans = cont.apply(new Function<Integer,
Either<Integer, String>>() {
public Either<Integer, String> apply(Integer x)
throws Failure {
return appE(tail, basis, x);
}
});
} catch(Exception ex) {
ans = new Right<Integer, String>("Failed with error " + ex);
}
return ans;
}
public static void main(String args[]) throws Failure {
eitherCPSdivBy0();
}
private static void eitherCPSdivBy0() throws Failure {
final Either<Integer, String> basis = new Left<Integer, String>(0);
final ResultE inf = new ResultE(basis);
looper(new Callee<Either<Integer, String>>() {
public Either<Integer, String> call(Integer inni)
throws Failure {
return inf.appEDivBy(new Function<Integer,
Either<Integer, String>>() {
public Either<Integer, String> apply(Integer x)
throws Failure {
return new Left<Integer, String>(x);
}
}, inni);
}
}, "either-CPS");
}
}
Note that it is the caller that determines what is 'good' (left) and what is 'bad' (right) and what to do in either case. And notice that in the below output, how simple and obvious everything is, we either have a left/number or a right/error condition.
javac -d .classes ResultE.java
java -cp .classes ResultE
Hey, for either-CPS (20 divBy 0 + 1) * 2 is Right<Failed with error java.lang.ArithmeticException: / by zero>
Hey, for either-CPS (20 divBy 1 + 1) * 2 is Left<42>
Hey, for either-CPS (20 divBy 2 + 1) * 2 is Left<22>
Hey, for either-CPS (20 divBy 3 + 1) * 2 is Left<14>
Hey, for either-CPS (20 divBy 4 + 1) * 2 is Left<12>
Hey, for either-CPS (20 divBy 5 + 1) * 2 is Left<10>
Hey, for either-CPS (20 divBy 6 + 1) * 2 is Left<8>
Hey, for either-CPS (20 divBy 7 + 1) * 2 is Left<6>
Hey, for either-CPS (20 divBy 8 + 1) * 2 is Left<6>
Hey, for either-CPS (20 divBy 9 + 1) * 2 is Left<6>
... aaaaaand we're done!
Apprennez le leçon, s'il vous plaît
So, okay, what's the take-away from all this? Besides the fact that Either is easy to implement and to apply and that lifting continuations to monadic binding is hard?
Well, just that. The previous two chapters are a reinvention of the ContT, the continuation monadic transformer, where I developed a need or justification for its use and then I wrote the thing out by hand from scratch.
THEN I looked up ContT in the Haskell standard library.
The journey of Haskell programmers is reimplementing functionality of the standard libraries. Enlightenment comes when they realize they are doing just that.
But I'm actually feeling pretty good from all this exercise. I never saw the 'point' before of continuations, and I never 'got' ContT; I didn't even look at it as a thing, and now, it's ... 'Ah! A Kleisli arrow on the continuation function! Now I see!" and I didn't see the 'point' of the Either type. It was just choice. So what?
Choice is a powerful thing. It's more than just error handling, as we have and show here, but even just that is powerful enough: it's simple to implement and easy to apprehend.
Continuations. It's shown us ... well, continuations, but the control pattern also exposes opportunity to explore data types that are very simple to use, but why? Because the patterns that arise beg the simplicity that are filled by these data types.
That's what I like about these simple concepts: rigorously applied, they open new vistas, yes, but they also facilitate the exploration with these patterns that allow us to try something, ContT, perhaps, and if that doesn't work well, then, well, how about Either, then? Or perhaps Maybe? Or a monadic or comonadic List? An applicative functor?
An universe of space to explore, and, with these tool, a (type-)safe, fun and exciting set of ways to branch off in these explorations.
I'll see you on the other side.
Next chapter. Tuples? Coroutining with continuations? We shall see.
-----
(1) In most cases, it is so that the output of functions is what concerns us. That's a reason monads are so pervasive: they allow us to control the output of functions safely in the monadic domain.
(2) This was my personal little crisis. I just couldn't see the point of functor types not carrying a datum. I mean: what did that look like? I was stuck on the idea of functor-as-id, and id carried a value it identified, even if it were the empty/null/unit-type instance. Same for monads. Yes, monads are the triple {T, μ, η} but if they aren't carrying a datum, what's the point? Monads not carrying a value seemed to be a rather abstract (and pointless) exercise to me. After all, even Nothing has a value: Nothing.
But that's where I missed it, right? But I'm in good company: the ancient Greeks looked upon the concept of zero as anathema and heretical. 'Something' exists, and 'nothing' doesn't exist. It can't. Conceptualizing it is error.
Or so they thought, and so did I. And looked what that blocking ... block? Math was stuck until zero was admitted, and then from zero, came everything ('infinity'). Same for me. By forcing Functor and, consequently, Monad to have arg(), I was boxing Functor into having something that it mayn't, and forcing Monad into something that it isn't: you extract from comonads, to extract from a monad is an error.
Let's look at Nothing again.
Nothing :: Maybe a
Nothing has the (Maybe'd) a-type, but it doesn't carry an a-instance.
Same thing for any kind of list:
[] :: [a]
The empty list has the (listed) a-type, but it doesn't carry an a-instance. It's an error to ask to extract an a-instance from an empty list.
Same thing for any mzero (dependent) (sub) type of a monoidally-typed (or -kinded) type.
So, whereas before I would have arg() for monads and throw an error when I encountered a Nothing or [] or other mzero-value, now I'm thinking that arg() depends on the type of the value. There's no arg() for [] and none for Nothing, either, and it's now a compiler error to ask for an arg() from those values. You just can't ask for arg() from Maybe nor from list any more when they're monadic, you have to obey the math of monads now, and fmap() the monadic function against the monad itself, then join() to get the monadic result.
Much cleaner, and now provably correct, because now the above doesn't yield a runtime error. When this new concept of monads is applied in programs, compiling the program successfully means it works now.
And this reconceptualization means I can now explore monads that do not carry an underlying value. I can have some monad m that itself has values m1, m2, m3, ..., mn and those (monadic) values, themselves, have their own intrinsic meaning: I don't have to ask() for their arg()ed values for the context of them: I can now use comonads for that when I need that.
Where will this new understanding lead me?
I don't know. I'm excited to find that out for myself.
No comments:
Post a Comment