Wie kann man prüfen, ob ein String kleiner als der andere ist, in Haskell?

Question

Ich habe zwei Strings als Argument für eine Haskell-Funktion gegeben.

s1 kleiner als s2 wenn s1 kürzer als s2 oder wenn sie die gleiche Länge haben und s1 lexikographisch kleiner als s2.

Wie implementiere ich dies in Haskell?

Answer 1

ich so etwas wie die folgenden verwenden würde:

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

Hier ist ein Probelauf, in Umarmungen:

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

Answer 2

Die One-Pass-Lösung:

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

Versuchen Sie folgendes:

compare s1 s2

(Dies gibt LT, EQ oder GT).

Answer 4

Eine kürzere Version der mappend Version von Tom Lokhorst oben:

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

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

Eine weitere Möglichkeit, die Vorteile der Bestellung von Tupeln unter:

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

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

Answer 5

String ist eine Instanz von Ord und daher können Sie verwenden alle diese Methoden zu vergleichen, um lexikografisch String. Wie Andrew sagte, ist, dass im Wesentlichen compare sondern auch die Vergleichsoperatoren, (<) unter anderem.

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

Dies funktioniert für alle Typen Umsetzung Ord (und ist eigentlich nur eine grobe Wrapper für (<)), einschließlich String.

Answer 6

Die normale Zeichenfolge vergleichen funktioniert nur auf lexikographische Ordnung, nicht die Länge von Strings.

So müßten Sie Ihre eigene Funktion schreiben, auch für die Länge zu überprüfen:

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

oder etwas allgemeiner:

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

Beispiel:

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

---

Wir waren Herumspiele mit Monoide an der Universität letzte Woche, und wir kamen mit dieser schönen alternativen Ord Instanz up:

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

Aber wenn Sie nicht ganz verstehen, empfehle ich Sie mit der ersten Definition halten; -)