Solution
= Solution
The <right fold> replaces the two <list> constructors by its two arguments; the <left fold> instead updates an accumulator while traversing the <list>.
``
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr c z [] = z
foldr c z (x:xs) = c x (foldr c z xs)
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl s a [] = a
foldl s a (x:xs) = foldl s (s a x) xs
``
Thus \b[`foldr` is the natural <list fold>]: it preserves the constructor arrangement while replacing `[]` by `z` and `(:)` by `c`. In particular, `foldr (:) [] = id`. More generally, the <fold factorisation criterion> says that the defining equations characterize the corresponding <structural recursion>. Association and <lazy evaluation> are separate: the accumulator in this definition of <left fold> is not automatically evaluated at each step.<Haskell 2010 Language Report>[Chapter 9, PreludeList: foldr and foldl]{ref}