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.

Fyodor Soikin · Accepted Answer · 2024-01-11 17:56:39Z

2

@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.

answered Jan 11, 2024 at 17:56

Fyodor Soikin

81.3k10 gold badges134 silver badges179 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Brian Berns · Accepted Answer · 2024-01-11 18:46:18Z

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.)

edited Jan 11, 2024 at 18:46

answered Jan 11, 2024 at 16:11

Brian Berns

17.3k2 gold badges33 silver badges45 bronze badges

Collectives™ on Stack Overflow

Stack overflow when composing functions in F#

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related