Implementing foldl with foldr

Introduction

Recently I am following an introductory course for Haskell: CIS 194 ¹ at UPenn. While doing the assignments, I came up with this problem: define foldl using foldr.

After spent about half an hour trying to figure this out, I was left frustrated. Then, I searched on Haskell wiki and found the answer, which is this small piece of code:

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f a bs =
    foldr (\b g x -> g (f x b)) id bs a

How to interpret this code? Let’s run a small example with the code. For brevity, we denote the function (\b g x -> g (f x b)) with w in below:

foldl (+) 0 [1,2,3] =>
    (w 1 (w 2 (w 3 id))) 0 =>
    (w 1 (w 2 ((\b g x -> g (f x b)) 3 id))) 0 =>
    (w 1 (w 2 (\x -> id ((+) x 3)))) 0 =>
    (w 1 (w 2 (\x -> (+) x 3))) 0 =>
    (w 1 ((\b g x -> g (f x b)) 2 (\y -> (+) y 3))) 0 =>
    (w 1 (\x (\y -> (+) y 3) ((+) x 2))) 0 =>
    (w 1 (\x ((+) ((+) x 2) 3))) 0 =>
    ((\b g x -> g (f x b)) (\y ((+) ((+) y 2) 3)) 1) 0 =>
    (\x (\y ((+) ((+) y 2) 3)) ((+) x 1)) 0 =>
    (\x ((+) ((+) ((+) x 1) 2) 3)) 0 =>
    ((+) ((+) ((+) 0 1) 2) 3) =>
    ((+) ((+) 1 2) 3) =>
    ((+) 3 3) =>
    6

Magical, isn’t it?

In my opinion, the key here is g, which “saves” the results from foldr and insert them as argument for function f, so that they will be used in reverse order.

1. This course is super great. I highly recommend it to new Haskellers. ↩