Как проверить, меньше ли строка, чем другая, в Haskell?

Question

У меня есть две строки в качестве аргументов для функции Haskell.

s1 меньше s2, если s1 меньше s2 или если они имеют одинаковую длину, а s1 лексикографически меньше s2.

Как мне реализовать это в Haskell?

Answer 1

Я бы использовал что-то вроде следующего:

smaller :: String -> String -> Bool
smaller s1 s2 | len1 /= len2         = (len1 < len2)
              | otherwise            = (s1 < s2)
              where (len1, len2) = (length s1, length s2)

Вот примерный прогон в объятиях:

Main> smaller "b" "aa"
True
Main> smaller "aa" "b"
False
Main> smaller "this" "that"
False
Main> smaller "that" "this"
True

Answer 2

Однопроходное решение:

lengthcompare :: Ord a => [a] -> [a] -> Ordering
lengthcompare = lc EQ
 where
  lc lx [] [] = lx
  lc _ [] _ = LT
  lc _ _ [] = GT
  lc EQ (v:vs) (w:ws) = lc (compare v w) vs ws
  lc lx (_:vs) (_:ws) = lc lx vs ws

smaller :: Ord a => [a] -> [a] -> Bool
smaller s1 s2 = lengthcompare s1 s2 == LT

Answer 3

Попробуйте это:

compare s1 s2

(Возвращает LT, EQ или GT).

Answer 4

Укороченная версия Тома Локхорста mappend выше:

import Data.Monoid (mappend)
import Data.Ord (comparing)

compareStrings :: String -> String -> Ordering
compareStrings = comparing length `mappend` comparing id

Другой способ, воспользовавшись порядком кортежей:

import Data.Ord (comparing)
import Control.Arrow ((&&&))

compareStrings :: String -> String -> Ordering
compareStrings = comparing (length &&& id)

Answer 5

Обычное сравнение строк работает только в лексикографическом порядке, а не в длине строк.

Так что вам нужно написать свою собственную функцию, чтобы также проверить длину:

smaller :: String -> String -> Bool
smaller s1 s2 | length s1 < length s2 = True
              | length s1 > length s2 = False 
              | otherwise             = s1 < s2

Или немного более общий:

compareStrings :: String -> String -> Ordering
compareStrings s1 s2 | length s1 < length s2 = LT
                     | length s1 > length s2 = GT
                     | otherwise             = compare s1 s2

Пример:

ghci> compare "ab" "z"
LT
ghci> compareStrings "ab" "z"
GT

---

На прошлой неделе мы играли с моноидами в университете, и мы придумали этот прекрасный альтернативный экземпляр Ord:

instance Ord a => Ord [a] where
  compare = comparing length
              `mappend` comparing head `mappend` comparing tail

Но если вы не совсем понимаете это, я предлагаю вам придерживаться первого определения; -)

Answer 6

String является экземпляром Ord, и поэтому вы можете использовать все эти методы для лексикографического сравнения строк. Как сказал Эндрю, это, по сути, compare, но также и операторы сравнения, (<) среди других.

smaller :: Ord a => a -> a -> Bool
smaller a b = a < b

Это работает для всех типов , реализующих Ord (и на самом деле это просто грубая оболочка для (<)), включая String.