Tail-Recursive Foldr

Question

I'd like to write a tail-recursive foldr in f#, to take advantage of the tail-recursion optimization and learn more about functional programming.

I've written a tail-recursive foldl, and a foldr that isn't tail-recursive. I thought I could get a tail-recursive foldr by reversing the list fed to the function, then calling my tail recursive foldl on it, but this doesn't work because of the different order the function is supposed to be applied to.

let rec tail_recurse_foldl(list: List<'a>, func:('b -> 'a -> 'b), acc: 'b) =
    match list with 
    | [] -> acc
    | [x] -> func acc x
    | x :: xs -> tail_recurse_foldl(xs, func, func acc x)

and non tail-recursive foldr

let rec foldr(list: List<'a>, func:('a -> 'b -> 'b), acc: 'b) =
    match list with
    | [] -> acc
    | [x] -> func x acc
    | x::xs -> func x (foldr(xs, func, acc))

"this doesn't work because of the different order the function is supposed to be applied to.". Have you actually checked if this is true? — Sylwester
@sylwester I didn't explain this well. I used the Haskell foldr and foldl as references. These have these type signatures: foldl :: (a -> b -> a) -> a -> [b] -> a foldr :: (a -> b -> b) -> b -> [a] -> b Coding to those, you can't just reverse the list. The function foldr and foldl take have different signatures. foldl takes the accumulator first, foldr takes the accumulator second. However, on further thought, there are two caveats here 1) There may be some way to flip the signature of the foldr function to match foldl. 2) Nothing is holding me to that signature but convention. — TheCharnelGod
Ok. Know that foldl and foldr are older than Haskell. In Lisp, especially Scheme, there has been some flipping where R6RS followed the accumulator as last argument for foldr but both earlier and older version has the same signature, though I think this is because these are not curried lazy languages like Haskell. — Sylwester

Tomas Petricek Tomas Petricek · Accepted Answer · 2019-07-09T18:48:57

There are two ways of doing this. An easier one is just to reverse the list (which is a tail-recursive operation) and then run fold from the left. A more sophisticated one is to use continuation-passing style.

In the continuation-based version, you add an extra argument, continuation which is a function that should be called once the processing of the list finishes (so that you can put the func call inside this continuation, rather than having it on the stack).

let rec foldr(list: List<'a>, func:('a -> 'b -> 'b), acc: 'b, cont:'b -> 'b) =
    match list with
    | [] -> cont acc
    | x::xs -> foldr(xs, func, acc, fun r -> cont (func x r))

When we get an empty list, we just call the continuation with the initial state acc. When you have non-empty list, we call foldr (tail-)recursively and give it a continuation that will run func on the result and then report the final aggregated value using its own cont call.

Tail-Recursive Foldr

1 Answers