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

Question

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

s1 est inférieur à s2 si <=> est inférieur à <=> ou s'ils ont la même longueur et <=> est lexicographiquement inférieur à <=>.

Comment puis-je implémenter cela dans Haskell?

Answer 1

Je voudrais 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 exemple de parcours dans Hugs:

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

Answer 2

La solution en un seul passage:

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

Essayez ceci:

compare s1 s2

(Ceci retourne LT, EQ ou GT).

Answer 4

Une version abrégée de la mappend version de 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 de tirer parti de la commande de n-uplets:

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

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

Answer 5

String est une instance de Ord et par conséquent, vous pouvez utiliser toutes ces méthodes pour comparer lexicographiquement chaîne. Comme Andrew l'a dit, il s'agit essentiellement de compare mais également des opérateurs de comparaison, (<) parmi d'autres.

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

Ceci fonctionne pour tous les types qui implémentent <=> (et n'est en réalité qu'un wrapper brut pour <=>), y compris <=>.

Answer 6

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

Vous devez donc écrire votre propre fonction pour 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éral:

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 Monoids à l'université la semaine dernière et nous avons proposé cette belle alternative Ord:

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 vous en tenir à la première définition; -)