= Solution
The <map function> transforms each head and recursively processes the tail. A <right fold> combines a head with the result for its tail, whereas a <left fold> passes an updated accumulator into the recursive call. In <Haskell>:
``
import Prelude hiding (map, foldr, foldl, concat)
map f [] = []
map f (x:xs) = f x : map f xs
foldr op e [] = e
foldr op e (x:xs) = op x (foldr op e xs)
foldl op e [] = e
foldl op e (x:xs) = foldl op (op e x) xs
concat = foldr (++) []
``
The last <right fold> uses <list concatenation> to replace each outer cons by appending its inner <list>. Thus `concat [xs,ys,zs] = xs ++ (ys ++ (zs ++ []))`. Its <right fold> association matters: appending a <list> traverses its left spine, so these equations traverse each inner spine once on finite inputs. The concise answer is
$$
\boxed{\operatorname{concat}=\operatorname{foldr}\ (\mathbin{++})\ [].}
$$
Back to article page
