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.
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: 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 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