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.

  

   

How to fold Infinite List in Groovy - Functional Groovy with Fpiglet

Folding on infinite list. (To be exact, right-folding infinite list.)  That does sound impossible and is a frequently discussed puzzle that Haskell programmers enjoy.  How can you start at infinity and iterate backwards to the result?  Can it be done in Groovy as well?

We will use Fpiglet. The solution I am going to explain here is not as elegant as Haskell's but I think should be still quite interesting.  First some intro for all readers who are not familiar with functional terminology.

Introduction:  Fold and reduce functions are functional programming equivalent of 'iterator'.  Functional programs do not want to mutate anything so the fold functions provide a way to 'accumulate' new data from the list without mutating any state.  There are 2 ways to iterate over a list:  

• scan it from the beginning to the end (left fold/left reduce)
• scan if from the end to the beginning (right fold/right reduce)

Folding accepts initial value of accumulator, reducing takes first element of the list as accumulator. 

 foldL   (foldClosure, initAcc, list) -> finalAcc

 reduceL (foldClosure, list) -> finalAcc

where

  foldClosure(acc, element) -> newAcc

So the folding functions scan the list and for each element execute foldClosure passing it current accumulator and current element. The job of foldClosure is to create new version of accumulator so nothing is mutated.  I am sure you recognize similarity to Groovy Collection.inject(Object, Closure) and Collection.inject(Closure) because these are OO equivalents of foldL and reduceL.

Here is an example from Fpiglet, we use foldL to calculate smallest element in the list:

  assert 2 == reduceL({acc,b -> (b<acc)?b:acc}) << [4,10,2,7]

this does not look much better than Groovy code would so here is more of Fpiglet style:

 assert 2 == reduceL(MIN)<<[4,10,2,7]

This will scan the list (4,) 10, 2, 7.  If we wanted to scan the list (7,) 2,10,4 we would write this:

 assert 2 == reduceR(MIN)<<[4,10,2,7]

One difference is that with right-folds the folding function has parameters flipped:

  foldClosure(element, acc) -> newAcc

Infinity (and beyond?):   Fpiglet implements functional programming version of list which is lazy. That means that what is on the tail of that list is not evaluated until needed. This allows for creation of recursive lists (also called streams) which never end like all natural numbers:

  def naturalNums = naturalNumbers() 

Fipglet has special version of right-folds which work with infinite lists: foldXR and reduceXR.  

So lets go starting at infinity all the way back to 1 ;),  FRIST is one of predefined funcitons returning first argument :
  assert 1 == reduceXR(FRIST) << naturalNums

Lets find first natural number larger than 50 which can be divided by 7: 

 def foldClosure= f {b, acc -> (b>50 && b%7==0)? b: acc()}

 assert 56 == reduceXR(foldClosure) << naturalNums

It works!  But wait, I was not writing about curried functions for nothing in last 3 posts, this is better code example:

 def finder = f {predicate, b, acc -> 

         predicate(b) ? b: acc()

 }

 def res= reduceXR(finder{it%7==0 && it>50}) << naturalNums

 assert 56 == res

We have folded natural numbers all the way from infinity back into 56!

How it is done:

Functional lists are immutable and are created by prepending elements one in front of the other.

So a list like [4,10,2,7] can be written in Fpiglet like so:

  e(4) << e(10) << e(2) << e(7) << empty()

It is even more intuitive to see it using Haskell notation:

   4 : 10 : 2 : 7 : []  

or, to be more explicit

    4 : (10 : (2 : (7 : [])))

now I want to right-fold this list using folding closure, let us take something simple, we tried MIN, MODULO, let us try PLUS (+).   

Right folding the above list with + is equivalent to this:

      4 + (10 + (2 + (7 + [])))

Did you notice that I just replaced ': 'with '+' ? 

So for generic folding closure fc,  if I could only write  

     x 'fc' y  //instead of fc(x,y) 

we would get this:

    4 'fc' (10 'fc' (2 'fc' (7 'fc' [])))

Now imagine, what happens if for some values of x in fc(x,y), the result does not depend on y.  Like in our situation where predicate(b)is satisfied!  Then we get this:

    4 'fc' (10 'fc' (2 'fc' (...who cares...)))

The only issue is how do I know that fc does not care about second parameter?  reduceXR and foldXR pass second parameter (acc) as a closure!  To use accumulator, the closure needs to resolve it first.  It returns the new accumulated value of course, not a closure.  The logical signature for folding closure would look like this

  fc :: el -> (_->acc) -> acc //el -list element, acc -accumulator

Case solved!

It is not so good:

FoldXR and reduceXR implementation are prone to stack overflows.  This is true even for Haskell!   And it follows from the fact that we really are creating a long chain of composed functions!

There are other functional methods which work well on infinite lists, like map or filter. 

Here is a simple chain of Fpiglet code, which is stack overflow safe:

 def res= filter{it%7==0} << filter(LARGER(50)) << naturalNums

 assert [56] == funlistOutTake(1) << res

I hope you enjoyed this post and I invite you to check out Figlet.