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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
