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.