Is it correct to say that fold_left corresponds to tail recursion and fold_right to forward recursion?

Learning
1

I am curious. Is there a correspondence between fold_left and fold_right with tail and forward recursion?

I was reading some code for manual implementations of them and it seems fold_right implements forward recursion and fold_left implements forward. Is that right?

 let rec fold_left f a list =
 match list
 with
 | [] -> a
 | (x :: xs) -> fold_left f (f a x) xs;; 

 let rec fold_right f list b =
 match list
 with [] -> b
 | (x :: xs) -> f x (fold_right f xs b);;

since it seems that fold right starts executing only until it reaches the end of the list (the right end, which I am assuming this is why its called fold right). But starts collecting a compound collection computations of f x (recurse) that don’t get executed until the end. i.e. the recursion is done first.

With fold left it seems the computation is done FIRST then the recursion. I say that cuz we have

 fold_left f (f a x) xs

so we have to compute (f a x) first for the whole fold_left thing to even begin executing. Which reminds me of tail recursion. Since we are pass the value to compute first.

2

fold_left starts from the left (beginning of the list) and is tail-recursive. fold_right starts from the right (end of the list) and is not tail-recursive. See the manual of the List module.

1 Like