Wednesday, 27 June 2012

More playing with monads

This blog post will look at using the continuation monad to sum the nodes in a tree, and then look at a case where a more complex monad is needed.

The book Real World Functional Programming gave an example of an unbalanced tree, which was deeply nested such that recursing over the tree to sum the values would blow the stack:

clip_image001

clip_image002

The solution provided was to sum the tree using continuation passing:

clip_image003

This is now able to sum the tree without crashing, but the code doesn’t flow as well as in the original sumTree method. However, monads can come to the rescue again, in this case the continuation monad:

clip_image004

The code flow now is easier to understand. The continuation passing style and continuation monad turns the code flow inside out, which isn’t a big deal, but means that the func to perform on the result needs to be passed in:

clip_image005

Parallel sum

This is all well and good, but to exploit multicore machines, I want to take advantage of the parallelism in the tree summation algorithm, by summing the different branches of the nodes using tasks. A naïve implementation to do this may be:

clip_image006

The problem with this is that it runs slower than the sequential case for a large balanced tree –if there are only 4 cores in the system it’s counter-productive to create thousands of tasks. The current depth of the tree should be passed around, and tasks spawned until traversal reaches that depth:

clip_image007

This is now faster for a large balanced tree, but for the deeply nested unbalanced tree it throws a StackOverflowException. Note that sumTreeParallel coped with arbitrarily nested trees, as the work to be done no longer kept being pushed onto the stack.

More state is being passed around (the current depth), which is external to the main business logic – it does feel like the state monad could be used here. First though, this is fixed up so that it has the efficiency of the parallel summation, but can cope with arbitrarily deeply nested trees:

clip_image008

Urghhhh. The code is definitely more convoluted now – I played with using the state monad to pass the depth around, but it’s not tail recursive. I thought that it might be possible to make use of the continuation monad here, but the problem is, is that it really needs aspects of both the state and continuation monads. I’m not sure how monad combinations work in F#, but I thought I’d throw this out here to see if anyone shows me the light. The post The Mother of All Monads does say that all other monads could be implemented in terms of the continuation monad, but I couldn’t see an example of anyone implementing the state monad in terms of the continuation monad.

2 comments:

Richard Astbury said...

I am surprised how similar F# looks to Haskell. Does it share the same kind of features?

paul marfleet said...

@Richard Astbury. Haskell and F# come from the ML stable of languages, so they certainly share some common features. Both are statically types, and use Hindley-Milner type inference to reduce the need for explicit type annotations. Both support pattern matching, list comprehensions, parametric polymorphism, and monads (F# calls them computation expressions). However it's also important to emphasize the differences between the languages. Haskell is a pure, lazy, functional language. Side
effects are permitted, but the type system requires you to be explicit about where they take place. It does not support imperative or object-oriented programming paradigms. F#, on the other hand, is a non-pure, eager, multi-paradigm functional language. Functional programming techniques are prioritized, but you can comfortably write imperative, object-oriented code as well.