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

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
>
> 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:

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

```