Delimited continuations

Delimited continuations encoded as a parameterized continuation monad.

 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:

type Cont<'T, 'S, 'R> = Cont of (('T -> 'S) -> 'R)

type ContBuilder() = 
    member self.Return x = Cont (fun k -> k x)
    member self.Bind (c : Cont<_, _, _>, f : _ -> Cont<_, _, _>) =
        Cont (fun k -> let (Cont contf) = c in contf (fun v -> let (Cont contf') = f v in contf' k))

let delim = new ContBuilder()

let run (c : Cont<_, _, _>) = let (Cont contf) = c in contf id

let shift f  = Cont (fun k -> f k)

// Cartesian product example
let result = 
    delim {
        let! x = shift (fun k -> [1; 2; 3] |> List.collect k)
        let! y = shift (fun k -> ["a"; "b"; "c"] |> List.collect k)
        return [(x, y)]
    } |> run // [(1, "a"); (1, "b"); (1, "c"); (2, "a"); (2, "b"); (2, "c"); (3, "a"); (3, "b"); (3, "c")]

// Error example
let test n : Cont<int option, int option, int option> =
    delim {
        do! shift (fun k -> if n = 0 then None else k ())
        return Some (42 / n)
    } 

test 0 |> run // None

Multiple items
union case Cont.Cont: (('T -> 'S) -> 'R) -> Cont<'T,'S,'R>

--------------------
type Cont<'T,'S,'R> = | Cont of (('T -> 'S) -> 'R)

Full name: Script.Cont<_,_,_>

Multiple items
type ContBuilder =
  new : unit -> ContBuilder
  member Bind : c:Cont<'a,'b,'c> * f:('a -> Cont<'d,'e,'b>) -> Cont<'d,'e,'c>
  member Return : x:'f -> Cont<'f,'g,'g>

Full name: Script.ContBuilder

--------------------
new : unit -> ContBuilder

val self : ContBuilder

member ContBuilder.Return : x:'f -> Cont<'f,'g,'g>

Full name: Script.ContBuilder.Return

val x : 'f

val k : ('f -> 'g)

member ContBuilder.Bind : c:Cont<'a,'b,'c> * f:('a -> Cont<'d,'e,'b>) -> Cont<'d,'e,'c>

Full name: Script.ContBuilder.Bind

val c : Cont<'a,'b,'c>

val f : ('a -> Cont<'d,'e,'b>)

val k : ('d -> 'e)

val contf : (('a -> 'b) -> 'c)

val v : 'a

val contf' : (('d -> 'e) -> 'b)

val delim : ContBuilder

Full name: Script.delim

val run : c:Cont<'a,'a,'b> -> 'b

Full name: Script.run

val c : Cont<'a,'a,'b>

val contf : (('a -> 'a) -> 'b)

val id : x:'T -> 'T

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

val shift : f:(('a -> 'b) -> 'c) -> Cont<'a,'b,'c>

Full name: Script.shift

val f : (('a -> 'b) -> 'c)

val k : ('a -> 'b)

val result : (int * string) list

Full name: Script.result

val x : int

val k : (int -> (int * string) list)

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

val collect : mapping:('T -> 'U list) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.collect

val y : string

val k : (string -> (int * string) list)

val test : n:int -> Cont<int option,int option,int option>

Full name: Script.test

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<_>

type 'T option = Option<'T>

Full name: Microsoft.FSharp.Core.option<_>

val k : (unit -> int option)

union case Option.None: Option<'T>

union case Option.Some: Value: 'T -> Option<'T>

Raw view Test code New version

More information

Link:	http://fssnip.net/j8
Posted:	11 years ago
Author:	Nick Palladinos
Tags:	continuations , monads