On Feb 6, 2006, at 2:40 PM, Mieszko Lis wrote:

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.

Well, these would be desugared differently.... (x,y,z) === Tuple x (Tuple y (Tuple z ())) (x,(y,z)) === Tuple x (Tuple (Tuple y (Tuple z ())) ()) which maintains the distinction, just like in lisp (maybe I remember lisp syntax...) where '(x y z) is not the same as '(x '(y z))

bluespec classic implemented n-tuples this way, and the error messages were rather ugly. not to mention that explaining this to beginners feels like a "oh yeah, it's not clean, it was an easy hack" copout :)

I'm pretty sure GHC, at least, already does type synonym folding for error messages. I suspect the same or a similar mechanism could be used to resugar tuples for messages. I also don't think it's a copout. Set theory formulations of classical mathematics usually defines n-tuples using nested 2- tuples. At least one constructive formulation of mathematics I know of defines n-tuples as nested pairs (the Coq theorem prover, which also provides syntactic sugar). It's a nice clean inductive definition and effortlessly allows tuples of arbitrary length. 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. Why would anyone ever use a 15+ tuple? Well maybe you wouldn't, but perhaps a code generator would. Or maybe a joy interpreter would. etc. More disturbing is the complete inability to write general functions over tuples. You can't even play fancy typeclass tricks because tuple constructors are not related by the type system in any way -- you have to do it the hard way each and every time by writing out various versions at different arities until you get tired of typing. Or, if you are a little more industrious, you can write a code generator. Either way, your function can only be defined up to some fixed limit. 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. Rob Dockins

-- m

On Feb 4, 2006, at 11:03 PM, Robert Dockins wrote:

...

On Feb 4, 2006, at 7:56 PM, Pablo Barenbaum wrote:

...

An awkwardness in Haskell I would like to see solved in Haskell', is the fact that the behavior of tuple-like constructors must be either built-in or "limited".

One thing I recall seeing on haskell-cafe some time back was the notion that an n-tuple is semantically equivalent to n nested right-strict 2-tuples (essentially right-strict heterogeneous lists). Perhaps we should consider the idea of the tuple notation simply being syntactic sugar for nested right-strict 2-tuples. Consider:

data Tuple a b = Tuple a !b

-- (a,b) === Tuple a (Tuple b ())-- (a,b,c) === Tuple a (Tuple b (Tuple c ())) -- etc...

fst (Tuple x _) = x snd (Tuple x (Tuple y _)) = y

fst ('a',b') = 'a' snd (a','b) = 'b'

fst ('a','b','c') = 'a' snd ('a','b','c') = 'b'

fst ('a','b','c','d','e','f') = 'a' -- etc...

It seems like compiler cleverness could recover the identical strictness and unboxing information available now when the "shape" of the tuple is known at compile time.

...

As far as I can see, these are two issues:

1. There is not a way, for the programmer, to define infinite constructors for infinite associated types (such as (,) (,,) (,,,) ... / (a, b) (a, b, c) (a, b, c, d) ...) these must be built-in.

2. There is not a way to define functions operating on all of these types. Instead, different functions (like zip, zip3) must be defined. Something similar happens with liftM, liftM2, ... these are "limited".

It seems the language is lacking abstraction, or being misused, when the standard prelude issues this code:

zip :: [a] -> [b] -> [(a,b)] zip = zipWith (\a b -> (a,b))

zip3 :: [a] -> [b] -> [c] -> [(a,b,c)] zip3 = zipWith3 (\a b c -> (a,b,c))

Clearly, at least for a human being, it's redundant. I don't know if there already are proposals to solve this.

Sorry if I sound aggresive, I'm just trying to help. Excuse my English...

Best regards.

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

On Feb 7, 2006, at 11:29 AM, Bulat Ziganshin wrote:

Hello Robert,

Tuesday, February 07, 2006, 6:42:41 PM, you wrote:

...

...

...

More disturbing is the complete inability to write general functions over tuples.

RD> As I understand it, you still have to write down the instance RD> declarations when using '-fgenerics'.

only one generic instance. it's very much these ideas of using nested tuples, only with special syntax. below is my definitions of Binary class for types with only one constructor:

[snip] To cut an paste from the GHC manual: class Bin a where toBin :: a -> [Int] fromBin :: [Int] -> (a, [Int]) toBin {| Unit |} Unit = [] toBin {| a :+: b |} (Inl x) = 0 : toBin x toBin {| a :+: b |} (Inr y) = 1 : toBin y toBin {| a :*: b |} (x :*: y) = toBin x ++ toBin y fromBin {| Unit |} bs = (Unit, bs) fromBin {| a :+: b |} (0:bs) = (Inl x, bs') where (x,bs') = fromBin bs fromBin {| a :+: b |} (1:bs) = (Inr y, bs') where (y,bs') = fromBin bs fromBin {| a :*: b |} bs = (x :*: y, bs'') where (x,bs' ) = fromBin bs (y,bs'') = fromBin bs' Now you can make a data type into an instance of Bin like this: instance (Bin a, Bin b) => Bin (a,b) instance Bin a => Bin [a] OK. So Now I want a Bin instance for 3-tuples. I have to write down: instance (Bin a, Bin b, Bin c) => Bin (a,b,c) Fine. Now I want it for 4-tuples.... instance (Bin a,Bin b,Bin c,Bin d) => Bin (a,b,c,d) See the problem? Sooner or later (probably sooner) I'll get tired of typing. I have to write down an 'instance' declaration for each value of n. Clearly this can't generalize to all n. So say I'm willing to deal with that and further suppose some super-helpful person writes down all the instances up to n=15 (say) and gets them included in some standard library. Uh! Now I discover I need a 17- tuple instance. OK fine, I have to write down my own special 17- tuple instance. Suppose (stay with me here), at some later time I import a library written by someone else and they ALSO discovered a need for an instance of this particular class for 17-tuples. Now our instances overlap! Double Ugh! I need to remove one of the instances. Still the problem is that I can't perform type level induction on the shape of the tuple. However, I'm willing to concede that generics greatly simplifies the problem -- perhaps to the point where my objections are merely academic. OK. I'm really done now. Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG

Marcin 'Qrczak' Kowalczyk writes:

In my language Kogut there are only pairs, and larger tuples are expressed by nested pairs (biased in the same direction as lists, without an end marker of course).

I wonder whether the performance difference is really that significant. Short tuples seem to be much more common. Anyone could gather statistics about runtime usage of tuples of varying sizes?

I agree that most uses of tuples are small, and for these, a nested representation will not be so bad. But Robert was proposing a nested representation precisely for the case where the tuples are large (possibly machine generated), and it is in those cases that performance might start to matter. Regards, Malcolm

A much bigger problem is that treating n-tuples as nested 2-tuples doesn't actually let you treat them generically, which was the point of the proposed transformation. imagine you want to replace all the values in an n-tuple with zero, what type would it have? zero_out :: (Int,?) -> (Int,?) there is nothing you can put there which will let zero_out work on arbitrarily deep tuples, its recursive call will always need to be called on something of the appropriate type which means the nesting depth needs to be specified in the type signature. You can do something with classes, but then you might as well just use the class for general n-tuples. John -- John Meacham - ⑆repetae.net⑆john⑈

Robert Dockins wrote:

data Tuple a b = Tuple a !b

-- (a,b) === Tuple a (Tuple b ())-- (a,b,c) === Tuple a (Tuple b (Tuple c ())) -- etc...

A problem with this is that there's no way of supporting partially-applied tuple type constructors without some sort of type system extension. But maybe there's no reason to support this. Are there any situations where people use "(,) a" where they couldn't simply define a new product type? I rather like the following solution for traversable tuples: Introduce unboxed pairs (# a,b #) and unboxed unit (# #) into the language. Allow datatypes to be specialized at unboxed types. Define data Tuple a = Tuple a and let (a,b) = Tuple (# a,(# b,(# #)#)#) (a,b,c) = Tuple (# a,(# b,(# c,(# #)#)#)#) ... Then allow class instances to be declared at unboxed types and type parameters to be instantiated at unboxed types by doing compile-time specialization (like C++ templates), and voila. No problem of ordinary tuple access becoming less efficient, though some care would be needed to prevent typeclass-based traversal from taking O(n^2) time. Of course, the compile-time specialization part is a bit tricky. -- Ben