Monadic Piles of Coconuts

After reading the “coconut” problem over on my friend’s blog, I thought it would be fun to solve it with a silly brute force approach. First, go read his post and then come back here.

let take n =

    let m = n - 1 // give one to the monkey

    if m % 5 = 0 // can divide remainder evenly into fifths?

    then Some(4 * m / 5) // return remaining 4/5ths

    else None // not a solution

This explains what happens when each guy wakes up and takes his share during the night. If after giving the monkey one of the coconuts the remainder is not evenly divisible by five then this can’t be right. For example, starting with n=26 coconuts works – give the monkey one and take exactly 1/5th; leaving 20. But n=20 doesn’t work because 19 can’t be divided into 1/5ths. Next:

let coconuts n =

    match take n with // 1st guy takes his share

    | None -> None

    | Some(r1) ->

        match take r1 with // 2nd guy takes his share

        | None -> None

        | Some(r2) ->

            match take r2 with // 3rd guy takes his share

            | None -> None

             | Some(r3) ->

                match take r3 with // 4th guy takes his share

                | None -> None

                | Some(r4) ->

                    match take r4 with // 5th guy takes his share

                    | None -> None

                    | Some(_) -> // works out!

                        Some(n)

This runs the scenario, each guy waking up and taking his 1/5th (plus one for the monkey). If at any point the story fails to make sense then this function bails; returning None. If the whole thing works out then we return Some(n).

Now to solve the puzzle by pure brute force all we have to do is try a bunch of values for n.

let solution = Seq.pick coconuts {1..1000000}

Returning the first value (assuming well under one-million) for which coconuts return Some(n). Works! Pretty cool, but I’m sure Magi’s solution using some elegant mathematics will be much slicker. The point of this post though is to introduce monads!

The coconuts function is exceedingly annoying; not the least bit DRY. It would be nice to factor out the repeated:

match take foo with

| None -> None

| Some(bar) -> … // continue using bar

This looks suspiciously like the ‘maybe monad.’ Essentially try taking foo and if that fails then bail out with None for the whole enchilada, but if it succeeds then continue to the next step threading the result through. By ‘continue using bar’ what we’ll need is a continuation function passed in.

let bind n c = match n with None -> None | Some r -> c r

Simple enough. Notice how we pass the continuation (c) in and call it with the result (r). Now we can rewrite coconuts:

let coconuts n =

    bind (take n) (fun r1 ->

        bind (take r1) (fun r2 ->

            bind (take r2) (fun r3 ->

                bind (take r3) (fun r4 ->

                    bind (take r4) (fun _ -> Some(n))))))

This is an important concept. Make sure you walk though this and understand the shear mechanics of what we’ve done here.

It all works but it’s still quite ugly; deeply nested function calls (look at all those parenthesis!) and still exposing the Some/None ‘packaging’ in both take and coconuts. Computation expressions are perfect for this in F#. Don Syme has an excellent post on computation expressions. First, we need to make a Builder object:

type AttemptBuilder() =

    member b.Bind (n, c) = bind n c

    member b.Return v = Some(v)

    member b.Zero _ = None

let attempt = new AttemptBuilder()

This holds our bind function and a couple of other functions to further encapsulate all exposure of the Some/None ‘packaging’ mechanics. Now using this 'attempt' builder we can simplify the original take function; removing the explicit Some(…) packaging and we can leave off the else (implying a call to Zero):

let take n = attempt {

    let m = n - 1 // give one to the monkey

    if m % 5 = 0 // can we divide evenly into fifths?

    then return 4 * m / 5 } // return becomes attempt.Return(4 * m / 5)
// else becomes: attempt.Zero()

The most important thing is that we no longer have any mention of Some or None outside of the builder. We can simplify the coconuts function as well (and again no mention of Some/None):

let coconuts n = attempt {

    let! r1 = take n // attempt.Bind(take n, (fun r1 -> ... ))

    let! r2 = take r1 // attempt.Bind(take r1, (fun r2 -> ... ))

    let! r3 = take r2 // attempt.Bind(take r2, (fun r3 -> ... ))

    let! r4 = take r3 // attempt.Bind(take r3, (fun r4 -> ... ))

    let! _ = take r4 // attempt.Bind(take r4, (fun _ -> ... ))

    return n } // attempt.Return(n)

This looks a lot like a simple sequence of assignments but remember that if any of these ‘take’s fail then the whole computation magically returns None rather than continuing and eventually returning n (or rather, again magically, Some(n)). The de-sugaring rules for let! , return, and for if without an else expand out into just what we had before but instead we can work entirely within the monadic syntax. Beautiful.

This has been one of the simplest monads but perhaps you see a glimpse of the possibilities. The bind and return functions are the essence and can hide away any amount of complexity and flow control and take care of all the packing and unpacking of hidden values threaded through the computation.