Overflowing stack when composing lots of functions together

Question

Here is one way of flattening a binary search tree. Its problem is that the stack overflows when the large function it builds is finally applied to []. I would like to know if there is a reasonable way of fixing this code fragment without completely changing how it works. For example, it would not help make progress to build a custom composer that builds a tree of functions, then evaluates them using an explicit stack (since the problem already is to flatten a tree).

let flatten_k t =

    let rec f t (k:(list<'a>->list<'a>)->list<'a>) =
        match t with
        | Leaf -> 
            k (fun xs -> xs)

        | Bin (l,x,r) ->
            f l (fun fl -> f r (fun fr -> k (fl << (fun xs -> x::xs) << fr)))

    f t (fun g -> g [])

It may be that it's better to think about a simplified instance, though it may be harder to convincingly demonstrate a fix on it (since it does close to nothing, though at least it shows that function composition does overflow the stack):

let test_composition () =
   let mutable f = id
   for i=0 to 1000000 do
       f <- id << f // >> works fine for me
   printf "Functions return %d" (f 123)

Again, this question is not about how to flatten a tree. I can easily do that as follows, or in any number of purely imperative ways. I want to know if an approach based on accumulating a large function can be made viable for this particular problem. Many thanks.

 let flatten t =

    let rec f t acc cont =
        match t with
        | Leaf ->
            cont acc

        | Bin (l, x, r) ->
            f r acc (fun rs -> f l (x::rs) cont)

    f t [] id

Answer 1

Your tree flattening function is not tail recursive.

The composition of functions is not tail recursive. This is easy to see by unfolding your triple composition:

original:              fl << cons << fr
unfold compositions:   fun a -> fl (cons (fr a))
unfold nested calls:   fun a ->
                          let x = fr a
                          let y = cons x
                          fl y

As you can see, this function first calls fr and then does something non-trivial with its result. The last call to fl is tail-recursive, but the previous two are not. The return address needs to be kept on the stack while fr and cons are executing, no way around that.

This is not tail recursion. Tail recursion works by passing the result of the last call to the caller up the stack. Passing this result to yet another function as argument - that's a whole different thing.

As for how to fix it - you can't if you insist on using function composition. And if you don't insist on it - then you already have a solution.

As far as your contrived example - I think it fails because you're running it in FSI or something like that. I have verified it just now:

• If you compile it normally, it works fine.
• If you turn off optimizations, it fails with stack overflow.
• If you replace id with some non-tail-recursive function (e.g. fun x -> x+1), it also fails.