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.

• N_A: Are you running it in debug mode?
• MrD at KookerellaLtd: I am running in debug...let me update the question
• N_A: Running in debug = no tail call eliminatin.
• MrD at KookerellaLtd: It seems to crash even running as an app....when you say running in debug...do you mean running in the ide OR do you mean compiling to the debug config.
• MrD at KookerellaLtd: Actually it crashed in debug, as a debug release and as a release release.

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.

• MrD at KookerellaLtd: but it isnt that its..sorry...give me some minutes to work it out
• MrD at KookerellaLtd: OK....I sort of understand that.... (using the wrong syntax its) this is... ((([] ++ [1]) ++ [2]) ++ [3]), so retrieving the 1st elememt I have to go down 40000....let me run a different scenario though...because I am actually going (in my real code) ([] ++ ([1] ++ ([2] ++ [3]))
• MrD at KookerellaLtd: hmmmmm now I'm really confused...my real code uses a hand rolled difflist to ease the o(n*n) effieciency of the above concats...this works...the efficiency but...I still get the stack overflow....I'll go away and think.
• MrD at KookerellaLtd: acchhh.....but original code DOESNT get a stack overflow!...and runs in linear time....its my messing around with sequences to try to work out how they work that failed......double thanks.