[Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
Larry Evans
cppljevans at suddenlink.net
Mon Nov 24 08:23:22 EST 2008
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
More information about the Haskell-Cafe
mailing list