history of tuples vs pairs
I have a foggy memory that early ML had only binary pairing, nesting for n-tuples. Can anyone confirm this memory. If so, does anyone remember the rationale for going to n-tuples? Performance, perhaps? Similarly, did the Haskell designers consider pairs as an alternative to n-ary tuples? The reason I ask is that while ghc and libraries suppors n-tuples for some values of n, the support is generally incomplete and inconsistent. And some abstractions are very heavily biased toward pairing, particularly Arrow and the pair instances of Monad and Applicative. And of course, inclusion of fst and snd in the prelude but lack of similar standard functions for n-tuples with n>2. - Conal
Conal Elliott wrote:
I have a foggy memory that early ML had only binary pairing, nesting for n-tuples. Can anyone confirm this memory. If so, does anyone remember the rationale for going to n-tuples? Performance, perhaps?
In Isabelle HOL "*" is a right-associative (pair) type constructor. So "T1 * T2 * T3" is the same as "T1 * (T2 * T3)". Although the concept is minimal it is sort of asymmetric (wrt. associativity). Cheers Christian
2008/6/25 Conal Elliott
I have a foggy memory that early ML had only binary pairing, nesting for n-tuples. Can anyone confirm this memory. If so, does anyone remember the rationale for going to n-tuples? Performance, perhaps?
Similarly, did the Haskell designers consider pairs as an alternative to n-ary tuples?
I think performance was part of it: accessing the nth element of a
tuple is O(1), but the nth element of a nested pair is O(n).
On the other hand, you can't internally represent nested pairs as
n-tuples because of laziness. (a,(b,c)) has elements of the form
(x,_|_) that don't correspond to any triple.
--
Dave Menendez
On Wed, 2008-06-25 at 16:50 +0200, Conal Elliott wrote:
I have a foggy memory that early ML had only binary pairing, nesting for n-tuples. Can anyone confirm this memory. If so, does anyone remember the rationale for going to n-tuples? Performance, perhaps?
What is the difference between a list build up of Cons and a "tuple" made out of pairs? I think the latter wouldn't really add anything new. A question of my own: is there much difference between e.g. data MyData = MyData Int Bool Char and type MyData = (Int, Bool, Char) other than the syntax of course? Regards, Niels
On Wed, Jun 25, 2008 at 07:50:08PM +0200, Niels Aan de Brugh wrote:
On Wed, 2008-06-25 at 16:50 +0200, Conal Elliott wrote:
I have a foggy memory that early ML had only binary pairing, nesting for n-tuples. Can anyone confirm this memory. If so, does anyone remember the rationale for going to n-tuples? Performance, perhaps?
???What is the difference between a list build up of Cons and a "tuple" made out of pairs? I think the latter wouldn't really add anything new.
The difference is that all the elements of a list must be the same type, whereas nested tuples could have elements of any type. For example, (True, (6, 'c')) :: (Bool, (Int, Char)) and there is no corresponding three-element list. However, you're right in noting the similarity between lists and nested tuples -- in fact, this is exactly how lists are implemented in lisp (which is where we get the tern 'cons').
A question of my own: is there much difference between e.g. data MyData = MyData Int Bool Char and type MyData = (Int, Bool, Char) other than the syntax of course?
Conceptually, there is not much difference; these types are clearly isomorphic. Practically speaking, there are differences other than just the syntax. For example, in Haskell 98 you are not allowed to make class instances for type synonyms. Another big difference is that this: type MyData = (Int, Bool, MyData) is illegal, whereas this: data MyData = MyData Int Bool MyData is perfectly fine. -Brent
On Wed, Jun 25, 2008 at 02:24:57PM -0400, Brent Yorgey wrote:
On Wed, Jun 25, 2008 at 07:50:08PM +0200, Niels Aan de Brugh wrote:
On Wed, 2008-06-25 at 16:50 +0200, Conal Elliott wrote:
I have a foggy memory that early ML had only binary pairing, nesting for n-tuples. Can anyone confirm this memory. If so, does anyone remember the rationale for going to n-tuples? Performance, perhaps?
???What is the difference between a list build up of Cons and a "tuple" made out of pairs? I think the latter wouldn't really add anything new.
The difference is that all the elements of a list must be the same type, whereas nested tuples could have elements of any type. For example,
(True, (6, 'c')) :: (Bool, (Int, Char))
and there is no corresponding three-element list. However, you're right in noting the similarity between lists and nested tuples -- in fact, this is exactly how lists are implemented in lisp (which is where we get the tern 'cons').
The other difference is that nested tuples have the number of elements specified in the type, while lists do not. -- David Roundy Department of Physics Oregon State University
Yes, early ML had nested pairs. We introduced n-tuples in Lazy ML
because in a lazy language n-tuples are not isomorphic to nested pairs
(whereas they are in a strict language). So n-tuples are nasty
because they are not inductive, but they are in many ways much more
reasonable than lazy nested pairs.
BTW, early ML also had binary sums. Again, they are not isomorphic to
n-ary sums.
-- Lennart
2008/6/25 Conal Elliott
I have a foggy memory that early ML had only binary pairing, nesting for n-tuples. Can anyone confirm this memory. If so, does anyone remember the rationale for going to n-tuples? Performance, perhaps?
Similarly, did the Haskell designers consider pairs as an alternative to n-ary tuples?
The reason I ask is that while ghc and libraries suppors n-tuples for some values of n, the support is generally incomplete and inconsistent. And some abstractions are very heavily biased toward pairing, particularly Arrow and the pair instances of Monad and Applicative. And of course, inclusion of fst and snd in the prelude but lack of similar standard functions for n-tuples with n>2.
- Conal
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Lennart Augustsson wrote:
Yes, early ML had nested pairs. We introduced n-tuples in Lazy ML because in a lazy language n-tuples are not isomorphic to nested pairs (whereas they are in a strict language). So n-tuples are nasty because they are not inductive, but they are in many ways much more reasonable than lazy nested pairs.
although it is possible in a slightly different (and less left-right symmetric) way in Haskell: data P a b = P a !b pair: P Int (P Bool ()) triple: P Char (P Int (P Bool ()) single: P Bool () unit: ()
BTW, early ML also had binary sums. Again, they are not isomorphic to n-ary sums.
data E a b = L a | R !b data Z --since Haskell Prelude provides us with the unit type () but not the uninhabited "zero" type, I'll use GHC's EmptyDataDecls syntax for this. either: E Int (E Bool Z) 3: E Char (E Int (E Bool Z) 1: E Bool Z 0: Z Still, these don't have isomorphic *representations*: the efficiency is lacking. I wonder if it would be possible to allow {-#UNPACK#-} for those polymorphic arguments in such a way that either/both of the above were actually equivalent to n-tuple/sums. -Isaac
participants (8)
-
Brent Yorgey -
Christian Maeder -
Conal Elliott -
David Menendez -
David Roundy -
Isaac Dupree -
Lennart Augustsson -
Niels Aan de Brugh