Stack Overflow in F# Sequences

Not so long ago, I ran into a curious problem while writing some F# sequence code.

Let's consider a simple function that takes a list and produces a sequence of the reversed list.

let rec reverse l =
  seq { match l with
         |h::t -> yield!  reverse t
                  yield h
         |[] -> yield! Seq.empty
      }

Now let's try to count the number of elements of a very large sequence.

let ls = Seq.to_list (seq {for i in 1..10000000 -> i})

Seq.fold (fun acc _ -> acc+1) 1 (reverse ls)

And here, what happen? We get a stack overflow. Maybe the beginning of an explanation lies in the definition of reverse.

Looking at it, we can see that the recursive call

 yield!  reverse t

appears before yielding the current head of the list. So we have a recursive call that is not in tail position.

That explains the stack overflow.

A solution is to use continuation passing style to move the recursive call to a tail position.

let reverse l =
  let k0 () = Seq.empty
  let rec proc l kc =
     seq { match l with
             |h::t -> let kc' () = seq { yield h
                                         yield! kc()
                                       }
                      yield!  (proc t kc')
             |[] -> yield! kc ()
         }
  proc l k0

Now it works!