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?

0 votes

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?

0 votes

`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

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

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

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

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

...