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

0 votes
asked May 4, 2009 by kjv

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?

6 Answers

0 votes
answered Jan 4, 2009 by konrad-rudolph

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.

0 votes
answered Jan 4, 2009 by tom-lokhorst

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 ;-)

0 votes
answered May 4, 2009 by andrew-hare

Try this:

compare s1 s2

(This returns LT, EQ, or GT).

0 votes
answered May 4, 2009 by luke-woodward

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
0 votes
answered May 4, 2009 by ganesh-sittampalam

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
0 votes
answered May 4, 2009 by newacct

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)
Welcome to Q&A, where you can ask questions and receive answers from other members of the community.
Website Online Counter

...