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

[Luke Palmer]

On Sun, Nov 30, 2008 at 10:43 AM, Max Rabkin <max.rabkin at gmail.com> wrote:
> On Sun, Nov 30, 2008 at 9:30 AM, Luke Palmer <lrpalmer at gmail.com> wrote:
>>  cross :: [a] -> [b] -> [(a,b)]
>>
>> It's just kind of a pain  (you build [(a,(b,(c,d)))] and then flatten
>> out the tuples).  The applicative notation is a neat little trick
>> which does this work for you.
>
> It seems to me like this would all be easy if (a,b,c,d) was sugar for
> (a,(b,(c,d))), and I can't see a disadvantage to that.

This is a tricky and subtle question, actually.  It has to do with the
lifting of tuples; those two types have different domains.  For
example, the element in the latter:

  (1,(2,_|_))

Has no corresponding element in the former  (there is (1,2,_|_,_|_),
but that corresponds to (1,(2,(_|_,_|_))) ).

Now, if tuples in Haskell were unlifted, meaning (_|_,_|_) = _|_, then
there would be no issue.  But that has far-reaching consequences in
the language design, among which the "seq" function would have to be
eliminated (many people would not be opposed to this).  Also usage of
unlifted tuples can cause subtle space leaks.

Now, what all this domain theory has to do with practical issues, I'm
not sure.  But you can't just do a slick replacement, because it
changes properties of programs that did not know the difference.

Frankly, I would prefer what you propose as well (actually, I would
prefer it to mean (a,(b,(c,(d,())))), but it's the same idea).  But
the change is difficult and requires thought.

Luke