Haskell type with tuples

3
votes

This question is focused specifically on list of tuples.

I was using sort to sort a list of tuples; at first I thought ghci would raise an error or something, but instead I received a sorted list based on the first element of my tuple!

Prelude Data.List> :t sort
sort :: Ord a => [a] -> [a]
Prelude Data.List> sort [3,1,2]
[1,2,3]
Prelude Data.List> sort [(3,'c'), (1,'a'),(2,'b')]
[(1,'a'),(2,'b'),(3,'c')]
Prelude Data.List> sort [(3,'c',1), (1,'a',2),(2,'b',3)]
[(1,'a',2),(2,'b',3),(3,'c',1)]

The same happens to functions with similar behaviors like minimum but not to those like any. So I guess this is a syntax sugar (Haskell always has some syntaxes that I have no idea about), but I'm not sure if this applies to other (Foldable t, Ord a) => t a types, nor if this is a more generic feature.

How does Haskell treat a tuple of type (a,b) so that f :: ([a] -> [c]) can be apply to l :: [(a, b)]? And does this way apply to other data structures or this is more like list-only?

1
listhaskelltypestuples
Tuples are lexicographically Ordered: the first components is compared first. On a tie, the second components are compared, And so on. So a list of tuples is a list of ordered elements, and can be sorted. – chi
You might like my discussion of how to read types as two-player games in Why can a Num act like a Fractional?. In the terms used in that answer: the caller of sort :: forall a. Ord a => [a] -> [a] chooses a to be (Int, Char), then provides evidence that (Int, Char) is an instance of Ord. Type variables can be instantiated to be any (monomorphic) type, including Int and tuples and lists and trees and Bools and whatever floats your boat. – Daniel Wagner

1 Answers

3
votes

Short answer

There isn't any magic here. That is because functions you have considered are sort :: Ord a => [a] -> [a] and minimum :: (Foldable t, Ord a) => t a -> a. Here you can see context Ord a, and in your case this a is a tuple (a, b). There is instance for tuple (Ord a, Ord b) => Ord (a, b). That's why you can execute (1,3) < (2,4). That's why it's working. And this functions will work with, for example, list of Maybe a.

any has type Foldable t => (a -> Bool) -> t a -> Bool, and it's can work with list of tuples. For example, like so:

any ((== 1) . fst) [(1,3), (2,4), (3,5)]

But not so:

any (== 1) [(1,3), (2,4), (3,5)]