= Solution
The recursive <Cartesian product> is:
``
cpRec :: [[a]] -> [[a]]
cpRec [] = [[]]
cpRec (xs:xss) = [x:ys | x <- xs, ys <- cpRec xss]
``
The corresponding <right fold> is:
``
cpFold :: [[a]] -> [[a]]
cpFold = foldr step [[]]
where
step :: [a] -> [[a]] -> [[a]]
step xs acc = [x:ys | x <- xs, ys <- acc]
cp :: [[a]] -> [[a]]
cp = cpRec
``
The base `[[]]` is essential: there is one way to choose from no factors, namely the empty selection. For a nonempty outer list, choose its first coordinate and prepend it to each selection from the remaining factors. This also proves equality with the <right fold> by <structural induction>. An empty factor produces no selections.
Back to article page
