Come verificare se una stringa è più piccola di un'altra, in Haskell?

Question

Ho due stringhe fornite come argomenti a una funzione di Haskell.

s1 è più piccolo di s2 se <=> è più corto di <=> o se hanno la stessa lunghezza e <=> è lessicograficamente più piccolo di <=>.

Come posso implementarlo in Haskell?

Answer 1

Userei qualcosa di simile al seguente:

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

Ecco un esempio di esecuzione, in Hugs:

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

Answer 2

La soluzione one-pass:

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

Prova questo:

compare s1 s2

(restituisce LT, EQ o GT).

Answer 4

Una versione più breve della mappend versione di Tom Lokhorst sopra:

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

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

Un altro modo, sfruttando l'ordinamento delle tuple:

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

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

Answer 5

String è un'istanza di Ord e pertanto è possibile utilizzare tutti questi metodi per confrontare lessicograficamente la stringa. Come ha detto Andrew, questo è essenzialmente compare ma anche gli operatori di confronto, (<) tra gli altri.

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

Funziona con tutti i tipi implementando <=> (ed è davvero solo un wrapper grezzo per <=>), incluso <=>.

Answer 6

Il normale confronto di stringhe funziona solo sull'ordinamento lessicografico, non sulla lunghezza delle stringhe.

Quindi dovresti scrivere la tua funzione per verificare anche la lunghezza:

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

O un po 'più generale:

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

Esempio:

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

---

La scorsa settimana stavamo giocando con i Monoidi all'università e abbiamo trovato questa adorabile alternativa Ord istanza:

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

Ma se non lo capisci del tutto, ti suggerisco di seguire la prima definizione ;-)