Long back i read about a blog post explaining a beautiful use-case of
call/cc. It tried to solve on set of variables very elegantly, in a declarative style. I tried doing something similar in scala with
Cont monad. The result looked like this
The above code snippet tries to find pythogorean triples. In fact we can replace the condition and solve any constraint satisfaction problem which can be solved with back tracking. First of all lets see what continuations are.
Imagine a programming language which doesnt have return statements. How would functions look like?
Every function would take a function as a parameter to which it would pass the result to. The parameter function is called as Continuation. It can be thought of sort of like a callback.
In static typed languages, a continuation of
A is any function which takes
(A => R) and gives back an
R is bottom type, like
So lets see a simple example of sum of squares of 2 integers written with continuations.,
square functions looks clean. It expresses our intent clear, but the
sumOfSquares looks bit clumsy. But the structure of it says there could be a
Monad instance for the it.
We would first abstract
Cont as a class and implement
flatMap on it.
This would make the code much clearer than our original reference of
(A => R) => R since the type parameter
R in case of
run method is bound only when you call it. For instance following code snippet is valid in case the
Cont[Int] instead of
(Int => R) => R
Now going back to our Monad instance, lets implement
map on it, signature basically looks like this
What map does is, it transforms the result into something else, ie., we apply the transformation, before we call the next continuation. Its like calling a function on the return value of some function.
flatMap? whose signature is this
Its exactly similar to map is, except that even the transformation function follows the convention of not returning the result and instead takes a continuation. So we have our
map implementation like this,
We also have a get function in
Cont which basically turns a
Cont back into a real return value.
Why would anyone want to give back a
Cont when its easier to return a value back? Because clearly
Cont is way more powerful. You can choose to call the
cont parameter in a run function once, or multiple times or never at all. Thats exactly what we are going to do with our original pythagorean triple example,
choose function instead of returning a chosen value, gives back a
Cont. And the run function in that
Cont keeps calling the
cont parameter with each value until it finds the one which doesnt get an exception. And
check function is even simpler, it throws an exception everytime it get a false value.
Thus we keep trying for each combination of values for
c until we hit upon one which satisfies our check conditions.
The entire code is in here