StackOverflow in continuation monad

computation-expression, f#, monads

Solution

To fix your example, add this method to your definition of the monad:

member this.Delay(mk) = fun c -> mk () c

Apparently the part that overflows is the destruction of the large input list in the recursive call of `map`. Delaying it solves the problem.

Note that your second version puts the recursive call to `map` behind another `let!` which desugars to `Bind` and an extra lambda, in effect delaying the recursive call to `map`.

I had to pursue a few false trails before reaching this conclusion. What helped was observing that `StackOverflow` is thrown by `OCaml` as well (albeit at a higher `N`) unless the recursive call is delayed. While `F#` TCO has some quirks, `OCaml` is more proven, so this convinced me that the problem is indeed with the code and not the compiler:

let cReturn x = fun k -> k x
let cBind m f = fun c -> m (fun a -> f a c)

let map f xs =
  (* inner map loop overflows trying to pattern-match long lists *)
  let rec map xs =
    match xs with
      | [] -> cReturn []
      | x :: xs ->
        cBind (map xs) (fun xs -> cReturn (f x :: xs)) in
  map xs (fun x -> x)

let map_fixed f xs =
  (* works without overflowing by delaying the recursive call *)
  let rec map xs =
    match xs with
      | [] -> cReturn []
      | x :: xs ->
        cBind (fun c -> map xs c) (fun xs -> cReturn (f x :: xs)) in
  map xs (fun x -> x)

let map_fused f xs =
  (* manually fused version avoids the problem by tail-calling `map` *)
  let rec map xs k =
    match xs with
      | [] -> k []
      | x :: xs ->
        map xs (fun xs -> k (f x :: xs)) in
  map xs (fun x -> x)

Problem

Using the following continuation monad: ``` type ContinuationMonad() = member this.Bind (m, f) = fun c -> m (fun a -> f a c) member this.Return x = fun k -> k x let cont = ContinuationMonad() ``` I fail to see why the following gives me a stack overflow: ``` let map f xs = let rec map xs = cont { match xs with | [] -> return [] | x :: xs -> let! xs = map xs return f x :: xs } map xs id;; let q = [1..100000] |> map ((+) 1) ``` While the following doesn't: ``` let map f xs = let rec map xs = cont { match xs with | [] -> return [] | x :: xs -> let! v = fun g -> g(f x) let! xs = map xs return v :: xs } map xs id;; let q = [1..100000] |> map ((+) 1) ```

Original source