Tuesday, October 20, 2009

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!

1 comment:

gradbot said...

Storing data inside of a function is pretty neat. Brian goes into some good catamorphism examples using it. In this case kc doesn't have to be a function and the sequence can be passed as a parameter since the new sequence object itself is storing the extra data.