Re: Tuple-like constructors

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

Robert Dockins 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