Why can't I compare tuples of arbitrary length in Haskell?

Question

I know that there are predefined Eq instances for tuples of lengths 2 to 15.

Why aren't tuples defined as some kind of recursive datatype such that they can be decomposed, allowing a definition of a function for a compare that works with arbitrary length tuples?

After all, the compiler does support arbitrary length tuples.

Answer 1

You might ask yourself what the type of that generalized comparison function would be. First of all we need a way to encode the component types:

data Tuple ??? = Nil | Cons a (Tuple ???)

There is really nothing valid we can replace the question marks with. The conclusion is that a regular ADT is not sufficient, so we need our first language extension, GADTs:

data Tuple :: ??? -> * where
    Nil  :: Tuple ???
    Cons :: a -> Tuple ??? -> Tuple ???

Yet we end up with question marks. Filling in the holes requires another two extensions, DataKinds and TypeOperators:

data Tuple :: [*] -> * where
    Nil  :: Tuple '[]
    Cons :: a -> Tuple as -> Tuple (a ': as)

As you see we needed three type system extensions just to encode the type. Can we compare now? Well, it's not that straightforward to answer, because it's actually far from obvious how to write a standalone comparison function. Luckily the type class mechanism allows us to take a simple recursive approach. However, this time we are not just recursing on the value level, but also on the type level. Obviously empty tuples are always equal:

instance Eq (Tuple '[]) where
    _ == _ = True

But the compiler complains again. Why? We need another extension, FlexibleInstances, because '[] is a concrete type. Now we can compare empty tuples, which isn't that compelling. What about non-empty tuples? We need to compare the heads as well as the rest of the tuple:

instance (Eq a, Eq (Tuple as)) => Eq (Tuple (a ': as)) where
    Cons x xs == Cons y ys = x == y && xs == ys

Seems to make sense, but boom! We get another complaint. Now the compiler wants FlexibleContexts, because we have a not-fully-polymorphic type in the context, Tuple as.

That's a total of five type system extensions, three of them just to express the tuple type, and they didn't exist before GHC 7.4. The other two are needed for comparison. Of course there is a payoff. We get a very powerful tuple type, but because of all those extensions, we obviously can't put such a tuple type into the base library.

Answer 2

You can always rewrite any n-tuple in terms of binary tuples. For example, given the following 4-tuple:

(1, 'A', "Hello", 20)

You can rewrite it as:

(1, ('A', ("Hello", (20, ()))))

Think of it as a list, where (,) plays the role of (:) (i.e. "cons") and () plays the role of [] (i.e. "nil"). Using this trick, as long as you formulate your n-tuple in terms of a "list of binary tuples", then you can expand it indefinitely and it will automatically derive the correct Eq and Ord instances.