Declaring foldl ( from left) in terms of foldr (from right)

Question

I have foldl:

let rec foldl f lst acc = match lst with
  | [] -> acc
  | hd::tl -> foldl f lst (f hd acc)

and I have foldr:

let rec foldr f lst acc = match lst with 
  | [] -> acc
  | hd::tl -> f hd (foldr f tl acc);;

I want to declare foldl using foldr.

How could this be done?

Answer 1

Informally, according to your definitions,

foldl (+) z [a;b;c;d] = (d+(c+(b+(a+z))))
foldr (*) n [a;b;c;d] = (a*(b*(c*(d*n))))

and so we need

foldl (+) z   [a;b;c;d]
 = foldr (*) n [a;b;c;d]     z
 = (a*(b*(c*(d*n))))         z
 =    (b*(c*(d*n)))       (a+z)
 =       (c*(d*n))     (b+(a+z))
 =      ...
 =             n (d+(c+(b+(a+z))))
 =               (d+(c+(b+(a+z))))

and thus it must be

   (a*r) z = r (a+z)
   n     z = z

i.e., in pseudocode,

foldl plus z xs  =  foldr mult n xs z
  where
  n        = { z => z }
  mult a r = { z => r (plus a z) }

Now you can write this in your syntax.

---

Note that the standard fold_left uses the flipped order of accumulation compared to yours (which was also used in the previous version of this answer).

Answer 2

One of the things you have to bear in mind is commutativity. For operations like addition or multiplication, it doesn't matter.

(((1 * 2) * 3) * 4)

Is equivalent to:

(1 * (2 * (3 * 4)))

But, if we consider something like subtraction...

(((1 - 2) - 3) - 4)

Is definitely not equivalent to:

(1 - (2 - (3 - 4)))

# (((1 - 2) - 3) - 4);;
- : int = -8
# (1 - (2 - (3 - 4)));;
- : int = -2

Fortunately, we can flip a function that takes two arguments. The standard library defines Fun.flip, but it's easily implemented.

# let flip f a b = f b a;;
val flip : ('a -> 'b -> 'c) -> 'b -> 'a -> 'c = <fun>

So, we can flip f and reverse the input list:

foldr (flip (-)) [4; 3; 2; 1] 0
flip (-) 4 (foldr (flip (-)) [3; 2; 1] 0)
flip (-) 4 (flip (-) 3 (foldr (flip (-)) [2; 1] 0))
flip (-) 4 (flip (-) 3 (flip (-) 2 (foldr (flip (-)) [1] 0)))
flip (-) 4 (flip (-) 3 (flip (-) 2 (flip (-) 1 (foldr (flip (-)) [] 0))))
flip (-) 4 (flip (-) 3 (flip (-) 2 (flip (-) 1 0)))
flip (-) 4 (flip (-) 3 (flip (-) 2 (0 - 1)))
flip (-) 4 (flip (-) 3 (flip (-) 2 ~-1))
flip (-) 4 (flip (-) 3 (~-1 - 2))
flip (-) 4 (flip (-) 3 ~-3)
flip (-) 4 (~-3 - 3)
flip (-) 4 ~-6
~-6 - 4
~-10

And checking our logic:

# List.fold_left (-) 0 [1; 2; 3; 4];;
- : int = -10

The same logic can be applied to implementing foldr in terms of foldl.