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
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.
Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
More information about the Haskell-prime