Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How does Haskell order Strings?

I've recently been learning Haskell, and I noticed that the String type (or [Char]) can be ordered. For example, this is valid:

ghci> "foo" > "bar"
True
ghci> "?<>!" `compare` "[&*}"
LT

How does Haskell order Strings, and when would this functionality be useful?

like image 378
Ben Avatar asked Dec 03 '22 05:12

Ben


1 Answers

How does Haskell order Strings, and when would this functionality be useful?

Firstly, Char is an instance of Ord, given by equality primitives on the underlying primitive char type on the machine.

instance Ord Char where
    (C# c1) >  (C# c2) = c1 `gtChar#` c2
    (C# c1) >= (C# c2) = c1 `geChar#` c2
    (C# c1) <= (C# c2) = c1 `leChar#` c2
    (C# c1) <  (C# c2) = c1 `ltChar#` c2

then String is defined as a [Char] (list of Char), and lists in general have an ordering, if their elements have an ordering:

instance (Ord a) => Ord [a] where
    compare []     []     = EQ
    compare []     (_:_)  = LT
    compare (_:_)  []     = GT
    compare (x:xs) (y:ys) = case compare x y of
                                EQ    -> compare xs ys
                                other -> other

and that's it. Any list whose elements have any ordering will in turn by ordered.

Since Char is ordered by its underlying representation as a bit pattern, and lists are given by element-wise ordering of the lists, you thus see the behavior for String.

when would this functionality be useful?

For inserting Strings into data structures that are polymorphic, but require an Ordering method. The most notable are Set and Map.

like image 58
Don Stewart Avatar answered Dec 20 '22 00:12

Don Stewart