= Solution
The most general <polymorphic> <type signatures> and recursive definitions are:
``
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
infixr 5 ++
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
concat :: [[a]] -> [a]
concat [] = []
concat (xs:xss) = xs ++ concat xss
``
The <right fold> replaces constructors by a supplied step and seed; <list concatenation> replaces the end of its first argument by its second; flattening concatenates each inner <list>. In particular,
$$
\boxed{\operatorname{concat}=\operatorname{foldr}(\mathbin{++})[],\qquad xs\mathbin{++}ys=\operatorname{foldr}(:)\ ys\ xs.}
$$
The <right fold> allows different element and accumulator types; the <list concatenation> operations require one common element type.
Back to article page
