3 people like it.

Computation monad for mortals

Basic implementation of the continuation monad with explanation.

 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: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
/// https://stackoverflow.com/questions/40052256/how-does-continuation-monad-really-work/42062682#42062682

/// A continuation is a function that represents "the rest of the computation".
type Cont<'T, 'U> = ('T -> 'U)

/// An incomplete computation is a function which, when given a continuation,
/// will return a value.
type Inc<'T, 'U> = Cont<'T, 'U> -> 'U

/// Creates an incomplete computation that holds the given value.
let ret (t : 'T) : Inc<'T, _> =
    fun (cont : Cont<'T, _>) -> cont t

/// Composition of incomplete computations.
let bind (incT : Inc<'T, _>) (wrap : 'T -> Inc<'U, _>) : Inc<'U, _> =
    fun (contU : Cont<'U, _>) ->   // return an Inc, which is a function that takes a continuation as input
        incT (fun t ->             // force the given incomplete computation to cough up its wrapped value
            (wrap t) contU)        // re-wrap the raw value so it can be sent to the given continuation

/// Monad definition.
type ContinuationBuilder() =
    member __.Return(value) = ret value
    member __.Bind(inc, wrap) = bind inc wrap

/// Builder instance.
let continuation = ContinuationBuilder()

/// Continuation-ized version of Fibonacci function.
let rec fib n : Inc<int, _> =
    continuation {
        match n with
            | 0 -> return 0
            | 1 -> return 1
            | n ->
                let! x1 = fib (n - 1)
                let! x2 = fib (n - 2)
                return x1 + x2
    }

[<EntryPoint>]
let main argv =
    for i = 0 to 10 do
        fib i (fun x ->   // pass the continuation directly to the fib function
            printfn "%d: %d" i x)
    0
type Inc<'T,'U> = Cont<'T,'U> -> 'U

Full name: Script.Inc<_,_>


 An incomplete computation is a function which, when given a continuation,
 will return a value.
type Cont<'T,'U> = 'T -> 'U

Full name: Script.Cont<_,_>


 https://stackoverflow.com/questions/40052256/how-does-continuation-monad-really-work/42062682#42062682
 A continuation is a function that represents "the rest of the computation".
val ret : t:'T -> cont:Cont<'T,'a> -> 'a

Full name: Script.ret


 Creates an incomplete computation that holds the given value.
val t : 'T
val cont : Cont<'T,'a>
val bind : incT:Inc<'T,'a> -> wrap:('T -> Inc<'U,'a>) -> contU:Cont<'U,'a> -> 'a

Full name: Script.bind


 Composition of incomplete computations.
val incT : Inc<'T,'a>
val wrap : ('T -> Inc<'U,'a>)
val contU : Cont<'U,'a>
Multiple items
type ContinuationBuilder =
  new : unit -> ContinuationBuilder
  member Bind : inc:Inc<'a,'b> * wrap:('a -> Inc<'c,'b>) -> Inc<'c,'b>
  member Return : value:'d -> Inc<'d,'e>

Full name: Script.ContinuationBuilder


 Monad definition.


--------------------
new : unit -> ContinuationBuilder
member ContinuationBuilder.Return : value:'d -> Inc<'d,'e>

Full name: Script.ContinuationBuilder.Return
val value : 'd
val __ : ContinuationBuilder
member ContinuationBuilder.Bind : inc:Inc<'a,'b> * wrap:('a -> Inc<'c,'b>) -> Inc<'c,'b>

Full name: Script.ContinuationBuilder.Bind
val inc : Inc<'a,'b>
val wrap : ('a -> Inc<'c,'b>)
val continuation : ContinuationBuilder

Full name: Script.continuation


 Builder instance.
val fib : n:int -> Inc<int,'a>

Full name: Script.fib


 Continuation-ized version of Fibonacci function.
val n : int
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
val x1 : int
val x2 : int
Multiple items
type EntryPointAttribute =
  inherit Attribute
  new : unit -> EntryPointAttribute

Full name: Microsoft.FSharp.Core.EntryPointAttribute

--------------------
new : unit -> EntryPointAttribute
val main : argv:string [] -> int

Full name: Script.main
val argv : string []
val i : int
val x : int
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
Raw view New version

More information

Link:http://fssnip.net/7VQ
Posted:8 months ago
Author:Brian Berns
Tags: continuation , continuation passing , continuations , monad , monads