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

Question

Ho due stringhe fornite come argomenti per una funzione Haskell.

s1 è minore s2 se s1 è più corto s2 o se hanno la stessa lunghezza e s1 è lexicographically piccolo di s2.

Come implementarlo in Haskell?

Answer 1

mi piacerebbe usare qualcosa come il 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 Abbracci:

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

Answer 2

Prova questo:

compare s1 s2 

(Restituisce LT, EQ, o GT).

Answer 3

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 

Questo funziona per tutti i tipi di attuazione Ord (ed è in realtà solo un wrapper greggio per (<)), tra cui String.

Answer 4

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

Quindi dovreste scrivere la propria funzione di controllare anche per 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 

---

Eravamo in giro con i Monoidi a università la settimana scorsa, e ci si avvicinò con questa bella alternativa Ord esempio:

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

Ma se non capisco questo, vi consiglio di bastone con la prima definizione ;-)

Answer 5

La soluzione di un passaggio:

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 6

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

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

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

altro modo, sfruttando l'ordinamento delle tuple:

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

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