Как Haskell заказывает строки?

Question

Я недавно изучал Haskell и заметил, что можно заказать тип String (или [Char]).Например, это действительно:

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

Как Haskell заказывает String с, и когда эта функциональность будет полезна?

Answer 1

Как Haskell упорядочивает строки и когда эта функциональность будет полезна?

Во-первых, Char является экземпляром Ord, заданным примитивами равенства для базового типа примитивов на машине.

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

тогда String определяется как [Char] (список символов), и списки обычно имеют порядок, если их элементы имеют порядок:

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

и все. Любой список, элементы которого имеют порядок, будет, в свою очередь, упорядочен.

Поскольку Char упорядочен по своему базовому представлению в виде битового шаблона, а списки задаются поэтапным упорядочением списков, вы, таким образом, видите поведение для String.

когда эта функция будет полезна?

Для вставки строк в структуры данных, которые являются полиморфными, но требуют метода упорядочения. Наиболее заметными являются Set и Map .

Answer 2

Как в Haskell упорядочить строки,

Вот некоторые определения из Haskell Prelude .

Строки - это просто списки символов:

type String = [Char]

Символы упорядочены по их кодовой точке Unicode:

instance  Ord Char  where
    c <= c' = fromEnum c <= fromEnum c'

И списки сравниваются с использованием лексикографического порядка (неявно по структуре списка и определению автоматически получаемых Ord):

data [a] = [] | a : [a] deriving Ord -- not actually valid Haskell :)

instance Ord a => Ord [a]

и когда эта функция будет полезна?

Вам нужен экземпляр Ord, чтобы использовать такие вещи, как Map или Set.

Answer 3

2 списки сравниваются по лексикографическому порядку (т.е. слева направо), при условии, что каждый элемент является экземпляром класса типов Ord.Строки можно заказать, потому что можно заказать символ.

Попробуйте:

[1,2,3] < [2,3,4,5]

Answer 4

Я бы предположил, что это лексикографический порядок , вне зависимости от используемой кодировки символов.(Другими словами, «алфавитный» порядок с, для ASCII или других однобайтовых кодировок, 256-символьный алфавит.)