How to check if a string is smaller than another, in Haskell?

Question

I have two strings given as arguments to a Haskell function.

s1 is smaller than s2 if s1 is shorter than s2 or if they have the same length and s1 is lexicographically smaller than s2.

How do I implement this in Haskell?

Answer 1

I'd use something like the following:

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

Here's a sample run, in Hugs:

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

Answer 2

The one-pass solution:

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

Try this:

compare s1 s2

(This returns LT, EQ, or GT).

Answer 4

An shorter version of the mappend version by Tom Lokhorst above:

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

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

Another way, taking advantage of the ordering of tuples:

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

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

Answer 5

String is an instance of Ord and therefore you can use all of those methods to lexicographically compare string. As Andrew said, that's essentially compare but also the comparison operators, (<) among others.

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

This works for all types implementing Ord (and is really just a crude wrapper for (<)), including String.

Answer 6

The normal string compare only works on lexicographical ordering, not the length of strings.

So you'd have to write your own function to also check for the length:

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

Or a bit more general:

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

Example:

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

---

We were toying around with Monoids at university last week, and we came up with this lovely alternative Ord instance:

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

But if you don't quite understand this, I suggest you stick with the first definition ;-)