 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/functional-programming-design-and-analysis-of-algorithms/2/b/solution

Again use structural induction on the finite list. At [], both the right fold and the left fold return the seed

a

. If they agree on zs, then

foldr (\oplus) a (z : zs) = z \oplus foldr (\oplus) a zs = z \oplus foldl (\otimes) a zs = foldl (\otimes) (z \oplus a) zs = foldl (\otimes) (a \otimes z) zs = foldl (\otimes) a (z : zs) .

The third line uses part (a); the fourth uses equation (2). Thus the left-right fold equivalence is

foldr (\oplus) a xs = foldl (\otimes) a xs .

This is a statement about values on finite, total inputs. It does not assert equal evaluation costs or equal behaviour on infinite lists.

 New to topics? Read the docs here!