Stack overflow when composing functions in F#

Question

Basically, my problem is that I'm trying to compose a very large number of functions, so I'm creating a deep chain of composed functions. Here is my code:

let rec fn (f : (State -> State option) -> (State -> State option)) (n : int) acc =
    match n with 
    | 0 -> acc 
    | _ -> fn f (n - 1) (f << acc)

and I make a call to it:

let foo = fn id 10000000 id bottom

So, it does ten milion iteration and it should combining lots of functions. I know for sure that fn is tail recursive (at least, I hope so), but the execution goes stack overflow and I can't figure out why.

At this point, the problem should be the deep cobination. So I was hoping for suggestions, tips, everything.

Answer 1

@BrianBerns's answer explains what's going on here, but I'd like to add a possible remedy.

Rather than using an acc variable to accumulate the monstrous composition of functions, take the seed argument and actually apply the function at every step:

let rec fn (f : (State -> State option) -> (State -> State option)) (n : int) arg =
    match n with 
    | 0 -> arg
    | _ -> fn f (n - 1) (f arg)

The meaning of this function is the same as your original: it applies function f to arg n times.

It is still tail-recursive, but it doesn't build up a big chain of composed functions.

Answer 2

I think the problem becomes a lot clearer if you split foo into two steps:

let bar = fn id 10000000 id   // create huge chain of functions (this works)
let foo = bar bottom          // execute huge chain of functions (this goes boom!)

So fn is indeed tail recursive and it successfully executes, creating a mega-function of chained functions that I've called bar. However, bar is not tail recursive, so when you call it with bottom, it exhausts the stack.

Update: Since bar is fun x -> f (f (f ... f (acc x))), I think you'd be better off evaluating acc bottom directly (before calling the recursive function), rather than delaying acc by sending it to fn. (This is essentially what Fyodor is suggesting as well.)