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

[Andrea Vezzosi]

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.

On Mon, Nov 24, 2008 at 5:43 AM, Larry Evans <cppljevans at suddenlink.net>wrote:

> On 11/23/08 13:52, Luke Palmer wrote:
>
>> 2008/11/23 Larry Evans <cppljevans at suddenlink.net>:
>>
>>> http://www.muitovar.com/monad/moncow.xhtml#list
>>>
>>> contains a cross function which calculates the cross product
>>> of two lists.  That attached does the same but then
>>> used cross on 3 lists.  Naturally, I thought use of
>>> fold could generalize that to n lists; however,
>>> I'm getting error:
>>>
>>
>> You should try writing this yourself, it would be a good exercise.  To
>> begin with, you can mimic the structure of cross in that tutorial, but
>> make it recursive.  After you have a recursive version, you might try
>> switching to fold or foldM.
>>
>
> Thanks.  The recursive method worked with:
> -{--cross.hs--
> crossr::[[a]] -> [[a]]
>
> crossr lls = case lls of
>  { []      -> []
>  ; [hd]    -> map return hd
>  ; hd:tail -> concat (map (\h ->map (\t -> h:t) (crossr tail)) hd)
>  }
> -}--cross.hs--
>
> However, I'm not sure fold will work because fold (or rather foldr1)
> from:
>   http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#12
>
> has signature:
>
>  (a->a->a)->[a]->a
>
> and in the cross product case, a is [a1]; so, the signature would be
>
>  ([a1]->[a1]->[a1]->[[a1]]->[a1]
>
> but what's needed as the final result is [[a1]].
>
> Am I missing something?
>
> -Larry
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20081124/835fa1f8/attachment.htm