Catamorphisms, part eight

Brian's profileInside F#BlogGuestbookNetwork

< Previous Next >

June 16

Catamorphisms, part eight

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.Let(x,f) = f 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!

10:32 PM | Blog it

Comments (2)

Brian McNamara has turned off comments on this page.

	Brian McNamarawrote: Check out http://cs.hubfs.net/forums/thread/8198.aspx Dec. 13
	gary ngwrote: I am learning F# and found this continuation monad interesting. Though I have a bit of problem applying it to this http://www.haskell.org/all_about_monads/html/contmonad.html#definition How would I implement the callCC using your builder and write the haskell example in F# ? Dec. 9

Trackbacks

Weblogs that reference this entry

None