Continuation Monad

ContMonad

// Simple computations 

let read() = System.Int32.Parse(System.Console.ReadLine())
let double x = x*2
let print x = printfn "%d" x

(read >> double >> print)()


// Same computations using continuations

let read cont =
   let x = System.Int32.Parse(System.Console.ReadLine())
   cont x

let double x cont = cont(x*2)

let print x cont = cont(printfn "%d" x)

read (fun x-> double x (fun x' -> print x' (fun x''->x'')))


// Introducing bind

let (>>=) a f = a f

(read >>= double >>= print)(fun x->x)


// Using F# Computational Expression Syntax

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

let res = (cont {
            let! x = read
            let! x' = double x
            do! (print x')
          }) (fun x->x)


// Implementins QSort using continuations

let qsort list =
  let rec loop list cont =
    match list with
    | [] -> cont []
    | x::[] -> cont [x]
    | x::xs ->
      let l,r = 
        List.partition ((>) x) xs
      loop l (fun ls ->
      loop r (fun rs ->
        cont (ls @ (x::rs))))
  loop list (fun x -> x)

qsort [6;3;89;34;67;1;38]


// The same, using monadic syntax

let qsort list =
    let rec loop list =
        cont {
            match list with
            | [] -> return []
            | x::xs ->
                let l, r = List.partition ((>) x) xs
                let! ls = loop l
                let! rs = loop r
                return (ls @ (x::rs))
        }
    loop list (fun x -> x)

qsort [6;3;89;34;67;1;38]


// Factorial using monadic syntax

let fac n = 
    let rec loop n = 
      cont {
              match n with
              | n when n = 0I -> return 1I
              | _ -> let! res = loop (n - 1I)
                     return n * res
           }
    loop n (fun x -> x)

fac 100I