Inside F#

Brian's thoughts on F# and .NET

Catamorphisms, part eight

Posted by Brian on June 16, 2008

In the interest of completeness, I have to point out one thing I left out of the previous blog entry in the series.  Some of you may have wondered why I used the continuation monad in "Change5to0bst", but not in the definition of KFoldTree.  If you try writing KFoldTree as

let KFoldTree nodeF leafV tree =
    let rec Loop t = K {
        match t with
        | Node(x,left,right) -> return! nodeF x (Loop left) (Loop right) t
        | Leaf -> return! leafV t 
    Loop tree (fun x -> x)

(with the rest of the code unchanged since the previous blog entry,) you’ll discover you once again get a stack overflow.  Ack!  The good news is, this is just because I originally defined the monad slightly wrong.  The fix is simple; here is the corrected definition:

type ContinuationBuilder() =
    member this.Return(x) = (fun k -> k x)
    member this.ReturnFrom(x) = x
    member this.Bind(m,f) = (fun k -> m (fun a -> f a k))
    member this.Delay(f) = (fun k -> f () k)
let K = new ContinuationBuilder()

The only difference is the definition of Delay, which has undergone eta-conversion.  With the corrected definition of "K", the above code for KFoldTree works correctly.  I am posting this just for completeness and posterity, so no deep explanations or new material today. 

The end!


3 Responses to “Catamorphisms, part eight”

  1. gary said

    I am learning F# and found this continuation monad interesting.Though I have a bit of problem applying it to this would I implement the callCC using your builder and write the haskell example in F# ?

  2. dsouflis said

    Hello Brian, the whole post series is very helpful, as there is scarce hands-on material on the subject, and whatever academic treatment is there, is usually too theoretic and impenetrable. Pity you didn’t sum it all up with a final version of the whole sample code, although, if one wants to really study the subject, the time spent to walk through the eight posts and assemble it oneself is negligible.

    I must say you missed the chance to mention catamorphisms on mutually recursive types (I did not even find much _academic treatment_ on that), which would have been the case for the combination of Expr and Op, had you not delegated Op to the lower status of dumb data operated upon by the Expr stuff. You often state that generating catamorphisms is type-driven and can be automated, but any automatic processor of types would have to treat Op as a regular union type as well. To be fair, I’m not even sure how it could be done, but I’m going to try using catamorphisms upon a real AST comprised of tens of mutually recursive types, from a project of mine, and see how it goes.

    I’d also like to leave a word of caution for future readers of the post series: you frequently state how using continuations makes the code tail-recursive, but, if one tries out the code, it appears that this does not happen in Debug mode, which is the usual mode one uses in order to play with – and step through – sample code.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: