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],[

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.

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)}

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:

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 =

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)

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)) =>

acc1 = apply(acc0, b(knightMove)) =>

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

which is the same as

acc0 = m.pure(initVal) =>

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)

b(knightMove) << ... << b(knightMove) << m.pure(initVal)

and that is exactly what we wanted.

**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

}

}

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 positionsdef inNmovesAllPaths = f {n -> composeNtimes(n, b(knightPath)) <

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]

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)

assert 0 < length << filter(pathLeadsTo([6,3])) << inNmovesAllPaths(3)

So let me raise a bar a bit and ask this question:

def initialPath = m.pure([1,1])

def destination = [6,5]

def stoppingRule = {paths-> !(isEmpty<< filter(pathLeadsTo(destination)) << paths)}

**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(

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

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

assert ! isEmpty(shortestPaths)

println funlistOut << head << shortestPaths

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.

## No comments:

## Post a Comment