Tuple-like constructors

Robert Dockins robdockins at fastmail.fm
Tue Feb 7 10:42:41 EST 2006

On Feb 7, 2006, at 9:49 AM, Malcolm Wallace wrote:

> Robert Dockins <robdockins at fastmail.fm> writes:
>>> i would argue against treating tuples as pure syntactic sugar for
>>> nested pairs; since the nesting carries hierarchical information, i
>>> would expect (x,y,z) used in place of (x,(y,z)) to cause an error.
> Indeed, quite apart from anything else, transforming tuples into
> nested tuples changes the performance of access from constant-time
> into linear-time (using the right-nested transformation specified
> by Robert), or at best, log-time (using a balanced tree schema).
> This is highly undesirable.

I'm not convinced.  Because the tuples are right-strict you can  
aggressively apply unboxing to the spine and recover constant time  
access to tuples whose shape is known at compile time (which includes  
all Haskell tuple code currently written).  At the very least you can  
special case the shapes of tuples up to, say n=15, and hit all the  
cases that people really care about -- and still have a generic  
fallback for n > 15.  The transformation can be a merely *semantic*  
one.  You, the clever compiler writer, can do whatever you need to do  
to make it go fast so long as it respects the semantics, and spine- 
strictness gives you a fair amount to work with.

>> The copout (in my opinion) is the current system where tuples are
>> defined up to some set n (64 in GHC I think -- the report only
>> mandates 15), and if you want bigger tuples you're SOL.
> To address this problem, I think we should permit user-definition of
> tuple constructors with the expected syntax e.g.  (,,,,,), which is
> already accepted by at least some compilers (nhc98,yhc).

Right.  This solve the first part of the problem.

>> More disturbing is the complete inability to write general functions
>> over tuples.
>>               The only fully general solution is to use something
>> like template haskell which 1) is overkill 2) has ugly syntax (sorry
>> but it's true) 3) GHC only and 4) hard to learn.
> I don't believe you need to invoke the full awesome majesty of
> Template Haskell in this case.  Surely plain -fgenerics will suffice?
> I am hoping that some simple form of data-type generics will make it
> into the new standard.

As I understand it, you still have to write down the instance  
declarations when using '-fgenerics'.  So you are still limited by  
the amount of time you are willing to spend typing ;-)
For GHC at least you can exhaust the available tuple constructors,  
but what if we take your suggestion above and recognize arbitrary  
numbers of ',' in parens?  You can sprinkle in the appropriate  
instance declarations whenever you need them, but now you can get  
conflicts with multiple modules creating the same instance (and  
there's no way to block instance imports).  It's clearly an  
improvement (except that nobody seems to use it), but its not the  
solution in its full generality.

The root problem seems to be that there is no type level way to  
perform induction/recursion on the size of a tuple.  Maybe nobody  
cares but me, but I'd like to see generic curry and zip functions,  
etc.  It seems like data marshaling libraries could also benefit from  
"inductive" tuples.

Anyway, if nobody else speaks out in favor of this I'm going to drop  
it for now -- maybe this is something to look at for Haskell 2.

Rob Dockins

Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
           -- TMBG

More information about the Haskell-prime mailing list