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

Question

I know that there are predefined Eq instances for tuples from 2 to 15 in length .

Why are tuples not defined as some kind of recursive data type, so that they can be decomposed, which allows us to define a function for compare that works with arbitrary length tuples?

In the end, the compiler supports arbitrary length tuples.

Answer 1

You may ask yourself what type of this generalized comparison function is. First of all, we need a way to encode component types:

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

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

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

But we end with question marks. Two more extensions are required to fill the holes: DataKinds and TypeOperators:

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

As you can see, we need three types of system extensions for type encoding only. Can we compare now? Well, it is not so easy to answer, because in fact it is far from obvious how to write an autonomous comparison function. Fortunately, a class type mechanism allows us to use a simple recursive approach. However, this time we are not just returning to the level of values, but also to the type of level. Obviously, empty tuples are always equal:

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

But the compiler complains again. What for? We need another FlexibleInstances extension, because '[] is a specific type. Now we can compare empty tuples, which is not so important. 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 

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

A total of five system extensions to the system, three of which are simply for expressing a tuple type, and they did not exist before GHC 7.4. The remaining two are necessary for comparison. Of course, there is a gain. We get a very powerful type of tuple, but because of all these extensions, we obviously cannot put that type of tuple in 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 (:) (ie, "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," you can expand it indefinitely and automatically output the correct instances of Eq and Ord .

Answer 3

Type compare a -> a -> Ordering , which assumes that both inputs must be of the same type. Tuples of different phenomena are, by definition, different types.

However, you can solve your problem by approaching it with either HLists or GADT .

Answer 4

I just wanted to add ertes to the answer that you don't need one extension for this. The following code should be haskell98, as well as compatible with 2010. And the data types in it can be mapped one on one with tuples, with the exception of a singleton tuple. If you recurse after two tuples, you can also achieve this.

 module Tuple ( TupleClass, TupleCons(..), TupleNull(..) ) where class (TupleClassInternal t) => TupleClass t class TupleClassInternal t instance TupleClassInternal () instance TupleClassInternal (TupleCons ab) data (TupleClassInternal b) => TupleCons ab = TupleCons a !b deriving (Show) instance (Eq a, Eq b, TupleClass b) => Eq (TupleCons ab) where (TupleCons a1 b1) == (TupleCons a2 b2) = a1 == a2 && b1 == b2 

You can also just get the equation. Of course, this would have looked a little cooler with TypeOperators, but the haskell list system also had syntactic sugar.