CODEWITHSUNDEEP
haskelltypes
Mike Izbicki
Mike Izbicki

Reputation: 6366

Why is (a,b,c,d) not sugar for (a,(b,(c,(d,()))))?

It's clear that any n-tuple can be represented by a bunch of nested 2-tuples. So why are they not the same thing in Haskell? Would this break something?

Making these types equivalent would make writing functions on tuples much easier. For example, instead of defining zip,zip2,zip3,etc., you could define only a single zip function that would work for all tuples.

Of course, you can work with nested 2-tuples, but it is ugly and there is no canonical way to perform the nesting (i.e. should we nest to the left or right?).

Upvotes: 36

Views: 1986

Answers (2)

Philip JF
Philip JF

Reputation: 28539

The type (a,b,c,d) has a different performance profile from (a,(b,(c,(d,())))). In general, indexing into an n-tuple takes O(1) while indexing into an "hlist" of n nested tuples takes O(n).

That said, you should check out Oleg's classic work on HLists. Using HLists requires extensive, and somewhat sketchy, use of type level programming. Many people find this unacceptable, and it was not available in early Haskell. Probably the best way to represent an HList today is with GADTs and DataKinds

data HList ls where
  Nil  :: HList '[]
  Cons :: x -> HList xs -> HList (x ': xs)

This give canonical nesting, and lets you write functions that work for all instances of this type. You could implement your multi way zipWith using the same techniques as used in printf. A more interesting puzzle is to generate the appropriate lenses for this type (hint: use type level naturals and type families for indexing in).

I have considered writing an HList like library that used arrays and unsafeCoerce under the hood to get tuple like performance while sticking to a generic interface. I haven't done it, but it should not be overly difficult.

EDIT: the more I think about this the more inclined I am to hack something together when I have the time. The repeated copying problem Andreas Rossberg mentions can probably be eliminated using stream fusion or similar techniques.

Upvotes: 35

Andreas Rossberg
Andreas Rossberg

Reputation: 36098

The main problem with this in Haskell would be that a nested tuple allows additional values, due to laziness. For example, the type (a,(b,()) is inhabited by all (x,_|_) or (x,(y,_|_)), which is not the case for flat tuples. The existence of these values is not only semantically inconvenient, it also would make tuples much more difficult to optimise.

In a strict language, though, your suggestion is indeed a possibility. But it still introduces a performance pitfall: implementations would still want to flatten tuples. Consequently, in the cases where you actually construct or deconstruct them inductively, they would have to do a lot of repeated copying. When you use really large tuples, that might be a problem.

Upvotes: 23

Related Questions