Как проверить, меньше ли строка другой в Haskell?
Вопрос
У меня есть две строки, переданные в качестве аргументов функции Haskell.
s1
меньше, чем s2
если s1
короче, чем s2
или если они имеют одинаковую длину и s1
лексикографически меньше, чем s2
.
Как мне реализовать это в Haskell?
Решение
Я бы использовал что-то вроде следующего:
smaller :: String -> String -> Bool
smaller s1 s2 | len1 /= len2 = (len1 < len2)
| otherwise = (s1 < s2)
where (len1, len2) = (length s1, length s2)
Вот пример прогона в Hugs:
Main> smaller "b" "aa" True Main> smaller "aa" "b" False Main> smaller "this" "that" False Main> smaller "that" "this" True
Другие советы
Однопроходное решение:
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
Попробуйте это:
compare s1 s2
(возвращает LT, EQ или GT).
Укороченная версия 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)
String
является экземпляром Ord
и поэтому вы можете использовать все эти методы для лексикографического сравнения строк. Как сказал Эндрю, это, по сути, compare
, но также операторы сравнения, (<)
среди других.
smaller :: Ord a => a -> a -> Bool
smaller a b = a < b
Это работает для всех типов реализации <=> (и на самом деле это просто грубая оболочка для <=>), включая <=>.
Обычное сравнение строк работает только с лексикографическим упорядочением, а не с длиной строк.
Поэтому вам придется написать свою собственную функцию, чтобы также проверять длину:
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
Но если вы это не совсем понимаете, советую придерживаться первого определения ;-)