On 11/24/08 00:40, Andrea Vezzosi wrote:
It's more natural to consider the cross product of no sets to be [[]] so your crossr becomes:
crossr [] = [[]] crossr (x:xs) = concat (map (\h ->map (\t -> h:t) (crossr tail)) hd)
which we can rewrite with list comprehensions for conciseness:
crossr [] = [[]] crossr (x:xs) = [ a:as | a <- x, as <- crossr xs ]
then look at the definition of foldr: foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs)
and, considering (foldr f z) == crossr, you should derive the definition of f and z.
THANK YOU Andrea (and Luke) for prompting me to a solution: crossf::[[a]] -> [[a]] crossf lls = foldr (\hd tail -> concat (map (\h ->map (\t -> h:t) tail) hd)) [[]] lls The reason I'm interested in this is that the cross product problem came up in the boost newsgroup: http://thread.gmane.org/gmane.comp.lib.boost.devel/182797/focus=182915 I believe programming the solution in a truly functional language might help a boost mpl programmer to see a solution in mpl. I expect there's some counterpart to haskell's map, concat, and foldr in mpl and so the mpl solution would be similar to the above crossf solution. -kind regards to both of you, Larry