¿Cómo verificar si una cadena es más pequeña que otra, en Haskell?

Question

Tengo dos cadenas dadas como argumentos para una función de Haskell.

s1 es más pequeño que s2 si <=> es más corto que <=> o si tienen la misma longitud y <=> es lexicográficamente más pequeño que <=>.

¿Cómo implemento esto en Haskell?

Answer 1

Usaría algo como lo siguiente:

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

Aquí hay una muestra de ejecución, en Abrazos:

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

Answer 2

La solución de un solo paso:

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

Prueba esto:

compare s1 s2

(Esto devuelve LT, EQ o GT).

Answer 4

Una versión más corta de la versión mappend de Tom Lokhorst arriba:

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

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

Otra forma, aprovechando el orden de las tuplas:

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

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

Answer 5

String es una instancia de Ord y por lo tanto, puede usar todos esos métodos para comparar lexicográficamente la cadena. Como dijo Andrew, eso es esencialmente compare pero también los operadores de comparación, (<) entre otros.

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

Esto funciona para todos los tipos que implementan <=> (y en realidad es solo un contenedor crudo para <=>), incluyendo <=>.

Answer 6

La comparación de cadenas normal solo funciona en el orden lexicográfico, no en la longitud de las cadenas.

Por lo tanto, tendría que escribir su propia función para verificar también la longitud:

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

O un poco más general:

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

Ejemplo:

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

---

Estábamos jugando con Monoids en la universidad la semana pasada, y se nos ocurrió esta encantadora Ord instancia alternativa:

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

Pero si no comprende esto, le sugiero que se quede con la primera definición ;-)