Monadic Comprehensions in Groovy and Fpiglet

This post is continuing my last 2 posts about monads.   In this post we will look at Groovy DSL syntax (as implemented in Fpiglet) for monadic comprehensions.

Legend:
  f([1,2,3]) - converts list [1,2,3] to functional list with the same elements
  f(myClosure) - converts closure to curried function
  << - is functions composition and passing param to function in Groovy,
         it also has been DSL-ed to do other things in comprehensions.

What are comprehensions:
If monads are about putting things in a 'box', then monadic comprehensions are magically removing the box. Only there is no magic.  Comprehension is a polymorphic (works across all monads) syntax which lets you operate on monads using 'unboxed' values.
Here is a simple example using Fpiglet Maybe type:
  
  def res = comprehend {
    x << from{ just(3) }
    y << from{ just(2) }
    output{ just(x+y) }
  }

  assert just(5) == res

One thing that Maybe and Either are famous for is that they are a great alternative to handling exceptions and nulls.  Let us see a bit of that in action:

 Closure maybeDivide = f { Maybe num, Maybe den ->
     comprehend {
       x << from { num }
       y << from { den }
       restrict { y != 0}
       output{ just(x/y) }
     }
 }

 def sixDividedBy = maybeDivide(just(6))
 assert just(2) == sixDividedBy(just(3))
 assert nothing() == sixDividedBy(just(0))

I think this is very cool and much more elegant than using if statements or throwing exceptions!

Fpiglet supports another syntax (somewhat LINQ inspired) which is also quite readable:

 Closure maybeDivide = f { Maybe num, Maybe den ->

   select{just(x/y)}.from {

      x << { num }

      y << { den }

      where { y != 0}

   }    

 }

Both versions are equivalent.  I will use select syntax moving forward.   

I hope you have enjoyed my Learn You a Haskell book inspired knight examples in previous posts. 

Here is a definition of knightMove function expressed using comprehension (please recall that positions are modeled as 2D Groovy lists [x,y] where x,y are in 0..7 range, but the list of all outcomes is a functional list):

 def knightMove = {pos ->

   def (x,y) = pos 

   select{ f([newPos]) }.from{ 

     newPos << {f([[x+2,y+1],[x+2,y-1],

                   [x-2,y+1],[x-2,y-1], 

                   [x+1,y+2],[x+1,y-2], 

                   [x-1,y+2],[x-1,y-2]]) }

     where {def (newX, newY) = newPos; newX in 0..7 && newY in 0..7}  

   }

 }

 assert [[2, 1], [1, 2]] == funlistOut << knightMove([0,0])

I am very much interested in code readability, so let me read the above code:

The result of knight move is select list (select {f[..]}) of new positions (newPos) from (.from) a list of spelled out positions ({f[...]}), where (where) the new position coordinates are in 0..7 range (newX in 0..7).

One of the reasons for having comprehensions is that they read very nice!

And here are all possible positions after 3 moves:

 def in3Moves = select { f([third]) }.from{

   first  << { knightMove([0,0]) }

   second << { knightMove(first) }

   third  << { knightMove(second) }

 }

I think it reads even better!

Summary:

In previous posts we did go beyond simple 3 time knightMove to solving problems like the shortest number of moves needed to move from A to B.  Stuff like this still requires folds.    

However comprehensions are a very powerful and very readable syntax.  

Please check out Fpiglet website in a few weeks for more information about Fpiglet monadic comprehensions.

Groovy, Monads, Knight, Chess. Making Groovy more functional with Fpiglet

In this post we will have some more fun with Groovy, chess, knights and monads using Fpiglet open source project.

This is continuation of my last post and will get a bit more advanced.  Please review my previous post first.

Legend:  Please remember that << in Groovy is function composition as well as parameter application:

 f(g(x)) //same as  f << g << x

and since we are using Fpiglet curried functions, we can be a bit more lenient with how we compose (curried functions are partially applied if invoked with fewer parameters).  Nothing was meta-programmed, Fpiglat monads are implemented purely using curried functions (it would be silly to use imparative code to implement monads!).  b is monadic bind (curried function) and m.pure is monad function which wraps object in monadic context.  Since we are talking about non-deterministic computing

  m.pure(x) //same as f([x]) (Fpiglet functional list with one element x)

Knights on Chessboard: This post is simply a more verbose version of unit tests that can be found in Fpiglet. The knight examples are inspired by Learn you a Haskell book. We have already seen how to use computational non-determinism to examine where knight can go on the chessboard. Here is somewhat improved version of knightMove which, now, includes chessboard boundary check:

Closure getKnightMove() {
 FunList possiblePositions = f([[1,2],[2,1],[-1,2],[2,-1],[1,-2],[-2,1],[-1,-2],[-2,-1]])
 Closure vplus = f {v, w -> [v[0] + w[0], v[1] + w[1]]}
 def onBoard  = {v -> def (x,y) = v;  x in 0..7 && y in 0..7 }

 return {v -> filter(onBoard) << map(vplus(v)) << possiblePositions}
}

 assert [[1,2], [2,1]] == funlistOut << knightMove([0,0])

Let me explain:  Positions on chess board are represented as [x,y] 2 element Groovy lists where x,y are in 0..7 range.  f (first line) if Fpiglet function, which maps Groovy List into functional Fpiglet FunList. This f is overloaded so f on second line converts closure to a curried function. (In general, f maps OO things to functional things.)  The result of knightMove([0,0]) will be a list (FunList) containing all positions  [x,y] where the knight can move from staring point [0,0]. 
That is why we call it non-deterministic computing.

So where can I go in 'n' moves?  We have seen this in previous post, but here is this code again:
 FunListMonad m = FunListMonad.instance

 def composeNtimes = f {n, Closure c -> reduceR(COMPOSE) << take(n) << repeat(c)}
 def knightNMoves = f {n, initVal-> composeNtimes(n, b(knightMove)) << m.pure(initVal)} 

 def allPositionsAfter3From0_0 = knightNMoves(3) << [0,0]

Short explanation: composeNtimes really does this:

  c << c << ... << c // n times

Now we simply use composeNtimes with b(knightMove) to accomplish monadic chain:

 b(knightMove) << b(knightMove) << .... << b(knightMove) // n times

Simple stuff!  Sorry if I bored you by repeating parts of my last post.
So here is another, more interesting, way to do the same thing using monadic left fold:       

 BaseM mf = BaseM.getInstance(FunListMonad.instance) //gets monadic functions

def knightNMoves =

       f {n, initVal-> mf.foldLM(apply,initVal)<< take(n)<< repeat(knightMove)}

that may require a bit of explanation.  First what is apply?  I need to answer this question with a question:  Is 5 a function?  

If f(5) is f applied with 5 why not think about it as 5 applied with f?  apply is Fpiglet function which does just this. Takes argument and applies function to it (all of these return the same value):

 apply(5, {it + 1})

 apply(5, PLUS(1))

 apply(5) << PLUS(1)
 PLUS(1)(5)

 PLUS(1,5) 

 {it + 1)(5)

The knightNMoves definition is equivalent to the following chain of fold operations (think of inject in Groovy, which is effectively left fold,  with monadic blows and whistles applied):

  acc0 = m.pure(initVal) =>
       acc1 = apply(acc0, b(knightMove)) => 

             acc2 = apply(acc1, b(knightMove))  =>...

which is the same as
  acc0 = m.pure(initVal) => 

       acc1 = b(knightMove)(acc0) => 

             acc2 = b(knightMove)(acc1) => ....

which in turn is equivalent to this:
      b(knightMove) << ... <<  b(knightMove) << m.pure(initVal)

and that is exactly what we wanted.

That is all very cool but, the code above gives us final positions of knight only. What if I wanted to see the full path, a list of moves that lead to the final position?

 Closure knightPath=  {path ->
     if(isEmpty(path)) {
        f [empty()] //list with empty list as element
     } else {
        FunList nextPos = knightMove(head(path))
        map(prepend(_, path), nextPos) //map partially applied on second position
     }
 }

Again somewhat straightforward stuff.  knightMove accepts single path, applies single knightMove to it to return a new list of possible paths. Last move is prepended in front.

Now we can do stuff like this:

  def initialPath = m.pure( m.pure([0,0])) //list of lists of positions
  def inNmovesAllPaths = f {n -> composeNtimes(n,  b(knightPath)) << initialPath} 

To do something meaningful we need to be able to check if a path ends where we want:
  Closure pathLeadsTo  =  f {v, path-> isEmpty(path)? false: v == head(path) }

so pathLeadsTo([x,y]) << path will check if path leads to [x,y]

How about, we check if we can get to [6,3] from [0,0] in 3 moves:
  assert  0 < length << filter(pathLeadsTo([6,3])) << inNmovesAllPaths(3)

So let me raise a bar a bit and ask this question:  what is the shortest sequence of moves that goes from [1,1] to [6,5]?

def initialPath = m.pure([1,1])
def destination = [6,5]
def stoppingRule = {paths-> !(isEmpty<< filter(pathLeadsTo(destination)) << paths)}

def shortestPaths =  filter(pathLeadsTo(destination)) << 

       mf.foldLMUntil(stoppingRule, apply, initialPath) << repeat(knightPath)

assert  ! isEmpty(shortestPaths)
println funlistOut << head << shortestPaths

Here is explanation:  We have used another Fpiglet function: a monadic fold with a stopping rule.    knightPath is placed in infinite sequence and we are folding this sequence with a stopping rule, which checks that we arrived at [6,5].  Otherwise the folding logic is the same foldLM logic we have seen already, one using function application.

So that code is no big deal!

I hope I have shown some power of monadic computing.  If it looks interesting check out Fpiglet.

Coding with Monads in Groovy, making Groovy more functional with Fpiglet

Monad is a quite simple concept yet is is perceived as a scary and complex thing that developers will never understand.  Fpiglet brings monadic computing to Groovy and the task should not be daunting at all.

History:  Monad concept came from Math, fortunately you do not need to understand much (or any) of Mathematics to understand and use monads.  In the nutshell, monads (in math, and in functional programming) are abstraction of 'container' concept.  Monad is simply a sophisticated term for a box.    If you know some Haskell you can read more about how math monads relate to monads used in programming: Haskell Understanding Monads (look at the end of that document).

What is it about:  It seems to me that functional programming is a simple concept that is made very confusing by all the attempts to express it using OO terms.  To any software engineer, Input-Output concept should be like bread and butter.  Functional programming is about transforming input to output.   The only trick is that these transformations are required to be pure (or safe) and are referred to as functions.
Pure/safe means that they do not change any state and do nothing else other than creating the output.

   data1 => function1 => data2 => function2 => data3 => ...

There is only one thing needed for that chain to work:  the result from function1 needs to match the input for function2...   This can be done by using bunch of tricks. One of them is the concept of curried functions (see my previous posts), another one is, yes, the monad.

In software we have a lot of boxes - we often put data into something that has additional context. Examples could be all the 'holder' classes which hold an object and some extra information.
One cool example is functional Either type which stores object or an error information why the object could not be created.  In this post, I will focus on one example that is very comprehensive and maybe one of the hardest to understand:  List as a Monad.

List as a Monad:
So putting a into a list [a] we are placing a into a box. It even looks like a box ;)
This allows as to think about 'a' in a wider context of non-deterministic computations.  Typically when you perform an operation you just expect one result.  But if you define an operation like this
  Closure eitherAddOrSubtract1 = {a ->  [a-1, a+1]}

you are defining a function which says that there is more than one possible outcome.

So let us play some chess.  If position of my knight on the chess board is [0,0] (Groovy 2-element List) I can write the possible set of next positions as this:
[[1,2],[2,1],[-1,2],[2,-1],[1,-2],[-2,1],[-1,-2],[-2,-1]]

(for simplicity I assume that chess board has no boundaries so I can move around in any direction).

We can define a knightMove function like so:
  FunList knightPositions= funlistIn << 
     [[1,2],[2,1],[-1,2],[2,-1],[1,-2],[-2,1],[-1,-2],[-2,-1]]
  
  //vector plus
  Closure vplus = f {a, b -> [a[0] + b[0], a[1] + b[1]]}

  def knightMove = {pos -> map(vplus(pos)) << possiblePositions}

(we are using Fpiglet here a bit, we are transforming Groovy list into a Functional List and use curried closures (see f in front of the closure) which can be applied with just one parameter even if they need 2. Please remember that << in Groovy is both closure composition as well as a way to pass argument to a closure)

It would be interesting to see where can I get in 3 moves.  So I would like to chain (compose) the calls to knightMove like so:

     knightMove << knightMove << knightMove << [0,0]

This will not work because knightMove output is a List of positions but input is a SINGLE position.

That seems more like artificial obstacle than anything else.  

This is what monad is about.  If you have a function (in a very pseudo code)

  fn: a  -> box a  //maps a to boxed a

then monad knows how to chain or compose it.  It does it by implementing a 'bind' function.

The following code in Fpiglet calculates a list of all possible knight positions after 3 moves

  Closure move3x= b(knightMove) << b(knightMove) << b(knightMove)

 FunList in3moves = move3x << [[0,0]] 

Bind function my look like magic, but it simply does what it says. It takes a function fn which accepts non-monadic type and returns a new function which accepts monadic type!  No rocket science (in very pseudo code):

  fn: a  -> box a  //or fn: T -> FunList<T>

  b(fn): box a  -> box a  //or b(fn):FunList<T> -> FunList<T>

To do that 'binding' monad implementation needs to figure out how the 'boxing' works. For lists this ends up being concatenating all possible results.  Now, these functions will compose just fine. 

And you can chain as much as you want:

  def composeNtimes = f {n, Closure c -> 

       reduceR(COMPOSE) << take(n) << repeat(c)

  }

  def inNmoves = f {n, initVal -> 

     composeNtimes(n,b(knightMove)) << [initVal]

  }

  def in4Moves = inNmoves(4,[0,0])

Notice that the above example uses right fold.  The same can be accomplished using monadic fold (which is left fold).  I will add a test case to Fpilget source demonstrating monadic fold solution in a few days.

Comprehensions: 

There is a more sophisticated idiomatic use of monads which I like to refer to as monadic comprehension.  You can do comprehensions with Fpiglet today, but most functional languages will give you some nice syntax sugar to make the code more readable.  

More info can be found on Fpiglet wiki pages, and I will write more at the time Fpiglet implements some syntax sugar for comprehensions.

-EDITED Aug 4, 2013- Fpiglet now implements simple monadic comprehension DSL!

You will find more examples of how to program with Monads in Fpiglet source code test folder.
I will be adding test code examples in the next few weeks.