Wednesday 16 December 2009

F# Continuation Monad (Tail Recursive Factorial)



// Continuation Monad in F#

type ContinuationMonad() =
    // ma -> (a -> mb) -> mb
    member this.Bind (m, f) = fun c -> m (fun a -> f a c)
    // a -> ma
    member this.Return x = fun k -> k x
    // ma -> ma
    member this.ReturnFrom m = m

let cont = ContinuationMonad()

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

printf "%A" (fac 100000I)

No comments: