如何在Haskell中检查一个字符串是否小于另一个字符串？

Question

我有两个字符串作为Haskell函数的参数。

如果s1比s2短或者它们长度相同且s1按字典顺序小于s2，那么s1就比s2小。

如何在Haskell中实现这个功能？

- kjv

Answer 1

我会使用以下类似的内容：

我会使用以下类似的内容：

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"
真
Main> smaller "aa" "b"
假
Main> smaller "this" "that"
假
Main> smaller "that" "this"
真

- Luke Woodward

---

这显然比我的版本快，因为它只计算字符串的长度一次。通过在输入字符串上进行直接模式匹配，可以将此定义与“length”函数的定义合并，从而可能使其更快。 - Tom Lokhorst

Haskell 的核心是泛化和良好编码规范，它有非常好的类型（类）系统。为什么不将函数重写为 compare' :: Ord a => [a] -> [a] -> Ordering 呢？ - Aleksandar Dimitrov

@Aleksander：这取决于OP想要什么。由于OP提出了一个相当基础的问题，也许他/她想要一个基础的答案？我不怀疑在Haskell中编写这样一个函数有更快和/或更习惯用的方法，但也许保持简单有助于帮助OP学习。 - Luke Woodward

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

- GS - Apologise to Monica

Answer 3

试试这个：

compare s1 s2

（这将返回LT，EQ或GT）。

- Andrew Hare

---

我认为 OP 希望短字符串比长字符串更“小”，而不考虑它们的内容。比较 "b" 和 "aa" 的结果是 GT，但我认为 OP 希望在这种情况下返回 LT 的函数。 - Luke Woodward

Answer 4

Tom Lokhorst上面的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)

- newacct

---

哦，对了，我在考虑另一种定义方式，但是在定义新函数时，你显然可以使用列表上的现有排序。很好的定义！ - Tom Lokhorst

另外，我真的需要开始学习Arrows库。我不断看到人们提出这些漂亮优雅的定义，而且仅使用函数实例就能做到这一点... - Tom Lokhorst

是的，这些代码很简洁。比较id == compare，所以这里有另一种选择：比较长度 mappend compare - Martijn

Answer 5

String 是 Ord 的一个实例，因此您可以使用所有这些方法来按字典顺序比较字符串。就像 Andrew 所说的那样，这基本上是 compare ，但也包括比较运算符，如 (<) 等。

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

这适用于所有实现了Ord的类型（实际上只是一个粗糙的(<)包装器），包括String。

- Konrad Rudolph

---

我认为OP希望较短的字符串比较长的字符串“更小”，而不考虑它们的内容。例如，较小的“b”和“aa”应该返回True。(<)不考虑长度，所以我不认为你的答案完全符合OP的要求。 - Luke Woodward

Answer 6

普通的字符串比较只能按照字典顺序排序，而不能按照字符串长度排序。

因此，您需要编写自己的函数来检查字符串长度：

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

上周我们在大学里研究了一下Monoids，然后我们想出了这个可爱的替代方案Ord实例：

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

但如果您还不太理解这个概念，我建议您坚持使用第一个定义 ;-)

- Tom Lokhorst

---

比较字符串长度的部分原因是许多其他语言中的String实现存储或缓存字符串长度。好处是大多数字符串比较将以字符串长度的函数O(1)的时间进行。但在Haskell中并非如此。所有使用本地实现的字符串比较都将至少以字符串长度的函数O(min(m,n))的时间进行。 - yfeldblum

当然，这甚至不是最快的实现方式。只是我认为提问者要求一个比较函数，在按字典顺序比较之前先检查字符串长度。如果你想打印一系列字符串，并认为先打印较短的字符串更漂亮，则可能会有用。 - Tom Lokhorst

@Tom：如果s2比s1更长，我不确定你的较小函数是否能正常工作。例如，较小的“aa”“b”返回True。在我看来，OP希望该函数在这种情况下返回False。 - Luke Woodward