Back to Questions
3.9k
views4
comments
Continuation Monad Composibility?
f#workflowswebmonadsmonad

I'm trying to learn workflow/monad syntax in f#. Here is the code

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
27
28
29
30
31
32
33
34

#light

// Pipeling functions
let square x = x * x
let plus3 x = x + 3
let result = square 4 |> plus3
printfn "%A" result

// Continuation passing style
let square_cps x k = k (x * x) 
let result_cps = square_cps 4 plus3
printfn "%A" result_cps

// Continuation workflow
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 cps = new ContinuationBuilder()

let square_cps_monad x = cps {return x * x}
let result_cps_monad = square_cps_monad 4 plus3
printfn "%A" result_cps_monad

// 1 - Advantage of workflow 
// does not require a new cps function definition for plus3 

let plus3_cps_monad x = cps {return x + 3}
let result_plus3_cps_monad = plus3_cps_monad 13 plus3
printfn "%A" result_plus3_cps_monad

System.Console.ReadLine()

How do i compose the cps {return x * x} and the cps {return x + 3} computations into a single computation? Is this even possible?

On a side note do people think referring to monads as workflows in F# is a good idea? Isn't this sort of like VB trying to come up with a "programmer friendly" name for refactoring? Every resource on the web refers to monads as monads, what gives?

.

Here's some sample code based on what you have

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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 cps = new ContinuationBuilder()

let square_cps_monad x = cps {return x * x}
let plus3_cps_monad x = cps {return x + 3}

let x_squared_plus_3_cps_monad x =
    cps {
        let! x_sq = square_cps_monad x
        let! r = plus3_cps_monad x_sq
        return r
    }
   
printfn "%A" (x_squared_plus_3_cps_monad 10 (fun x -> x))

Once you have functions like square_cps_monad, you can use them in a workflow with let! the same way you use normal functions in normal code:

1
2
3
4
5
6
7

// non-cps-monadic
let square x = x * x
let plus3 x = x + 3
let x_squared_plus_3 x = 
    let x_sq = square x
    let r = plus3 x_sq
    r

That's the kind of compositionality that the workflow syntax and Bind() give you.

See also

[link:lorgonblog.spaces.live.com]

[link:lorgonblog.spaces.live.com]

Regarding terminology, yeah, it's unfortunate in my opinion that they kinda have three names in F#: "workflows" (which on the platform can be confused with WF (Windows Workflow Foundation)), "computation expressions" (my favorite term for the F# monad syntax; this term seems to be losing ground in terms of mindshare), and of course just "monads".

By on 10/4/2008 12:52 AM ()

Thanks Brian. I believe have my brain wrapped around the syntax now.

1
2
3
4
5
6
7
8
9
10
11

// Still composable like regular functions except and we
// do not need to explicitly pass the continuation to each
// function
let square_plus3_cps_monad x =
    cps {
        let! rs = square_cps_monad x
        let! r = plus3_cps_monad rs
        return r
    }   
let result_square_plus3_cps_monad = square_plus3_cps_monad 4 plus3
printfn "%A" result_square_plus3_cps_monad

Outside of the cps monad both square_cps_monad and plus3_cps_monad require an explicit continuation be passed as a paramter. However, inside of the cps monad the continuation is passed implicitly. The plus3 function gets passed to both functions without having to explicitly pass it. Correct?

By on 10/4/2008 10:05 AM ()

Yes.

For each monad, the main thing the computation expression syntax buys you is that "let!" gives succinct syntax for Bind(), which does the work of plumbing together the bits of code in the monad. In the case of the continuation monad, the "work" is plumbing the continuation parameter through at each step. In the option/Maybe monad (on the other thread), the "work" is the bit that says, after each statement, if it's None then abort the rest of the computation, else continue with the Some value. Monads make the "work at each step (that's particular to this monad)" implicit.

By on 10/4/2008 12:57 PM ()

Gotcha. Here's an example of an identity monad i've thrown togther. I know it doesn't do any "work at each step", but it has helped me understand the scaffolding of the monad. The bind through me for a loop at first and really forced me to think through what is happening.

I think i'll do a blog post for other VB programmers learning F#. Please let me know if you see anything obviously wrong. Thanks in advance.

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
27
28
29
30
31
32

#light

type Identity<'a> = (unit -> 'a)

let id x = (fun () -> x) : Identity<'a>
let runIdentity (m : Identity<'a>) = m()
let bind m (f: 'a -> Identity<'b>) = f (runIdentity m)
let delay f = (fun () -> runIdentity (f ()))

type IdentityBuilder() =
    member b.Bind(m,f)  = bind m f
    member b.Delay(f) = delay f
    member b.Let(x,f) : Identity<'a> = f x
    member b.Return(x) = id x
    
let identity = new IdentityBuilder()

let square_monad x = identity {return x * x}
let plus3_monad x = identity {return x + 3}

let square_plus3_monad x =
    identity {
        let! rs = square_monad x
        let! r = plus3_monad rs
        return r
    }   
     
let result = runIdentity (square_plus3_monad 4)

printfn "%A" result

System.Console.ReadLine()
By on 10/6/2008 8:26 PM ()

    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