Back to Questions
3.2k
views3
comments
continuation monad and call/cc
f#haskellmonad

While reading brain's blog, I found this interesting piece

[link:lorgonblog.spaces.live.com]

which is an implementation of the continuation monad in F#

However, I have some problem adopting it to the Haskell implementation here

[link:www.haskell.org]

In comparision, this Scala implementation is closer to the haskell implementation which I can understand and work with

[link:lamp.epfl.ch]

Could anyone give me a hand on how to implement the call/cc and the example mentioned in the haskell page in F# ?

thanks in advance.

.

Honestly, I do not understand call/cc, but I think maybe this code will be enough to let you run with it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#light

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

let CallCC (f : (('a -> ('b -> 'r) -> 'r) -> ('a -> 'r) -> 'r)) : ('a -> 'r) -> 'r =
    (fun k -> f (fun a _ -> k a) k)

let SumList l =
    let rec Sum l =
        K {
            let! result = CallCC (fun exit1 -> K {
                match l with
                | [] -> return 0
                //| h::t when h=2 -> return! exit1 42  // uncomment this
                | h::t -> let! r = Sum t
                          return h + r
            })
            return result
        }
    Sum l (fun x -> x)

printfn "%d" (SumList [1;2;3])
By on 12/11/2008 9:04 PM ()

million thanks.

What confused me though is 'when to K or when not to K' ?

Both the haskell and Scala signature indicates that call/CC's return type is a continuation monad but your implmentation doesn't need the K even though it works just as it should.

By on 12/11/2008 10:45 PM ()

I didn't look at the Scala implementation.

Compared to Haskell, rather than introduce any new data type (e.g. 'Cont'), I just used the function type (('a->'r)->'r) as the representation type for the monad. Since the type is completely transparent, you can either program using the syntactic sugar of the K builder object to leverage F# computation expression syntax, or you can just program at the representation level (with huge ugly types, like the type of CallCC - I coded that by hand from the Haskell type by expanding "m", and used that to guide part of the implementation). In this case, I wrote CallCC at the representation level; I think this is maybe also the "traditional" approach for such monads (the 'built in primitives' are written based on the underlying implementation, whereas user code is written only in terms of M<'a>, computation expressions, and calls to the 'built in primitives').

Hmm, I dunno how much that last paragraph made sense; let me try again...

Back in part 2 of my parser series

[link:lorgonblog.spaces.live.com]

I describe the 'basis' for parsers as five functions. And then if you go look at the F# implementation

[link:lorgonblog.spaces.live.com]

you see that those 5 functions are coded 'directly against the representation', whereas all subsequent functions are written using either the "parse" builder object and F# computation expressions, or sometimes just calls to the basis functions or other combinators. And so if I rephrase "when to 'parse' and when not to 'parse'?", you don't use 'parse' when writing the core basis of the library, but you do use it whenever convenient in client code of the library. Code that doesn't use the builder object either (1) is part of the core library for this particular monad, and knows all the intimate details of the underlying representation (e.g. "CallCC" for 'K' or "sat" or "<|>" for 'parse'), or (2) is client code that uses functions/combinators on the monadic types directly without having to ever "bind" ("let!") (e.g. "letter").

I don't know that that made any more sense this time around. :)

By on 12/12/2008 12:29 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper