[Haskell-cafe] Re: howto tuple fold to do n-ary cross product?

[Larry Evans]

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