[Haskell-cafe] Re: howto tuple fold to do n-ary cross product?
Andrea Vezzosi
sanzhiyan at gmail.com
Mon Nov 24 01:40:55 EST 2008
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
More information about the Haskell-Cafe
mailing list