title: How to convert CPS-style gcd computation to use the Continuation Monad
body: <p>Let us consider the following implementation of the Continuation monad, for CPS-style computations yielding and integer:</p>
  
  <pre><code>module Cont : sig
    type 'a t = ('a -&gt; int) -&gt; int
    val return : 'a -&gt; 'a t
    val bind : 'a t -&gt; ('a -&gt; 'b t) -&gt; 'b t
    val callCC: (('a -&gt; 'b t) -&gt; 'a t) -&gt; 'a t
  end = struct
    type 'a t = ('a -&gt; int) -&gt; int
  
    let return x =
      fun cont -&gt; cont x
  
    let bind m f =
      fun cont -&gt; m (fun x -&gt; (f x) cont)
  
    let callCC k =
      fun cont -&gt; k (fun x -&gt; (fun _ -&gt; cont x)) cont
  end
  </code></pre>
  
  <p>How can we rewrite the CPS-style implementation of gcd computation (see <a href="https://stackoverflow.com/questions/25704901/how-to-memoize-recursive-functions/25705254#25705254">How to memoize recursive functions?</a>) and especially the memoization to take advantage of the Cont monad?</p>
  
  <p>After defining</p>
  
  <pre><code>let gcd_cont k (a,b) =
    let (q, r) = (a / b, a mod b) in
    if r = 0 then Cont.return b else k (b,r)
  </code></pre>
  
  <p>I tried to use the type solver to give me cue about the type that the memoization function should have:</p>
  
  <pre><code># let gcd memo ((a,b):int * int) =
    Cont.callCC (memo gcd_cont (a,b)) (fun x -&gt; x)
  ;;
      val gcd :
    (((int * int -&gt; int Cont.t) -&gt; int * int -&gt; int Cont.t) -&gt;
     int * int -&gt; (int -&gt; 'a Cont.t) -&gt; int Cont.t) -&gt;
    int * int -&gt; int = &lt;fun&gt;
  </code></pre>
  
  <p>However I could not turn this hint into an actual implementation. Is someone able to do this?  The logic behind using “callCC” in the memoization function is that if a value is found in the cache, then this is is an early exit condition.</p>