Why does this F# expression stack overflow

Question

let ints = [1..40000]

// create [{1};{2};.....{40000}]
let a1 = ints |> List.map Seq.singleton 

// tail recursively append all the inner list
let a2 = a1 |> List.fold Seq.append Seq.empty

// tail recursively loop through them
let a3 = a2 |> Seq.forall (fun x -> true) // stack overflow...why?

my reason for asking is concern that I have code that will recursively append and I need to be sure it wont blow up....so I ran this example in order establish what was going

both in debug and running as an app.

Answer 1

The first thing to note is that the function causing the SO exception is:

let a2 = a1 |> List.fold Seq.append Seq.empty

but you don't see the SO until you evaluate the next line because sequences are lazily evaluated.

Because you are using Seq.append, each new item you add to your sequence creates a new sequence which contains the previous sequence. You can construct a similar sequence directly like so:

> seq {
    yield! seq { 
                   yield! seq { 
                                  yield 1
                              }
                   yield 2
               }
    yield 3
}

val it : seq<int> = seq [1; 2; 3]

Notice how, to get to the very first item (1) you have to go to depth 3 of the sequence. In your case that would be depth 40000. The sequence isn't tail recursive, so each level of the sequence ends up as a stack frame when iterating it.