Is a List Sorted?

Question

This function checks if a list is sorted.

isSorted' :: (Ord a) => [a] -> [a] -> a -> Bool
isSorted' [] [] _ = True
isSorted' (x:xs) [] _ = isSorted' xs xs (head xs)
isSorted' orig (x:xs) a
 | a > x = False
 | otherwise = isSorted' orig xs a

I don't like how this function requires that the list be entered twice. But, I need to check all items of the list.

For example, if I only checked if the head was greater than any of the other items, then the following could happen:

[-5, 10, -6] -- check only first element and will evaluate to true
--

But, we'll find out that this list is not sorted given the fact that 10 is greater than -6.

[10, -6] -- evaluates to False

How can I simplify/clean up this function?

• Jerry Coffin: The classic formulation would be something like: the first item in the list is less than the second, and the rest of the list (after the first item) is sorted.
• abuzittin gillifirca: Did you write this function? Looking at the prime (') in the function name and the auxiliary parameters; this function clearly is supposed to be called from a wrapper function like this: isSorted xs = isSorted' xs xs (head xs) (trivial case ignored) Although still badly written (clunky and inefficient) the wrapper has the correct type signature, so that you do not need to pass the input list twice.

Answer 1

Generally, when you're using explicit recursion in Haskell, there is an easier way. There are many higher order function that will do this recursion for you (map, fold and filter being the quintessential examples).

In this case, we want to go through the list, checking each element against the next element. Whenever you want to do something on a list element and the next list element, you should start thinking of zip: this takes two lists and "zips" them together. For example:

zip [1, 2, 3] [4, 5, 6] == [(1, 4), (2, 5), (3, 6)]

In this case, we want to offset this by one, however. The easiest way of doing this is to simply use tail:

zip xs (tail xs)

So if we had a list like:

[1,2,3,4]

This would give us back:

[(1, 2), (2, 3), (3, 4)]

Ok, so now we have this list of pairs that we need to compare. Instead of using recursion and pattern matching, we'll use a higher order function: in this case, all is what we're looking for. This has the type signature:

all :: (a -> Bool) -> [a] -> Bool

Ok, so this takes a function from (a -> Bool) and a list of a, and gives back a Bool.

Now, all we need to do is decide on the function (a -> Bool). In this case, it's pretty simple: we just want to take a tuple of two values and check if the first is less than the second. We can write this succinctly using a lambda:

(\(x, y) -> x <= y)

Putting this all together, we get:

isSorted :: (Ord a) => [a] -> Bool
isSorted xs = all (\(x, y) -> x <= y) $ zip xs (tail xs)

• Simon Bergot: isSorted xs = and $ zipWith (<=) xs (tail xs)