Search code examples
f#functional-programming

How does continuation monad really work


I understand how Reader or Maybe or State monads work, but havig hard times with Continuations monad. Examples like below, blow my head

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

I think that my problem is that I cannot get what is a monadic type for Continuation (like Cont<'T>) and how i can unwrap it and wrap back. Any helpful examples or links are highly appreciated.


Solution

  • I will not repeat what has been said elsewhere - the post mentioned in the comments gives a lot of details about the continuation monad. But one thing that might help is to rewrite your code snippet with an explicit definition for Cont<'T>:

    type Cont<'T> = 
      Cont of (('T -> unit) -> unit)
    

    The type Cont<'T> represents a computation. You can start it by giving it a function 'T -> unit that takes the result and does something with it (say, prints it). When you start it, it returns unit and it will (at some point) produce a value 'T and call the continuation you provided.

    With this more explicit definition, the builder can be defined as:

    type ContinuationMonad() =
       member this.Bind (ma, f) = 
          Cont(fun k -> 
            let (Cont ca) = ma
            ca (fun a -> 
                let (Cont cb) = f a
                cb k))
    
       member this.Return x = 
          Cont(fun k -> k x)
    
    • The Return member creates a computation that, when given a continuation k, calls this continuation immediately with the value x that we returned.

    • The Bind member returns a new computation that, when given a continuation k, starts the computation specified by m; when this computation produces a value a, it calls the function f and then calls the computation returned by f with the original continuation k (which is the "final" continuation that should eventually be called with the final result).