CODEWITHSUNDEEP
functional-programmingf#
TheCharnelGod
TheCharnelGod

Reputation: 65

Tail-Recursive Foldr

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

Upvotes: 0

Views: 1299

Answers (1)

Tomas Petricek
Tomas Petricek

Reputation: 243126

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.

Upvotes: 6

Related Questions