Comment vérifier si une chaîne est plus petite qu'une autre, dans Haskell?

Question

J'ai deux chaînes données comme arguments à une fonction Haskell.

s1 est plus petit que s2 si s1 est plus courte que s2 ou si elles ont la même longueur et s1 est lexicographique plus petit que s2.

Comment l'implémenter dans Haskell?

Answer 1

I'D utiliser quelque chose comme ce qui suit:

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

Voici un échantillon analysé, dans étreintes:

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

Answer 2

Essayez ceci:

compare s1 s2 

(Ce retour LT, EQ ou GT).

Answer 3

String est une instance de Ord et vous pouvez donc utiliser toutes ces méthodes pour comparer une chaîne lexicographiquement. Comme Andrew a dit, c'est essentiellement compare mais aussi les opérateurs de comparaison, (<) entre autres.

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

Cela fonctionne pour tous les types la mise en œuvre Ord (et est vraiment juste un emballage brut pour (<)), y compris String.

Answer 4

La comparaison de chaînes normales ne fonctionne que sur l'ordre lexicographique et non sur la longueur des chaînes.

Vous devriez écrire votre propre fonction de vérifier également la longueur:

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

Ou un peu plus générale:

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

Exemple:

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

---

Nous étions en train de jouer avec les monoïdes à université la semaine dernière, et nous sommes arrivés avec cette belle solution de rechange Ord exemple:

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

Mais si vous ne comprenez pas tout à fait cela, je vous suggère de tenir à la première définition ;-)

Answer 5

La solution 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 6

Une version plus courte de la version mappend par Tom Lokhorst ci-dessus:

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

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

Une autre façon, en tirant parti de l'ordre de tuples:

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

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