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.