6
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Jerry Coffin Apr 8 '14 at 2:34
  • \$\begingroup\$ 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. \$\endgroup\$ – abuzittin gillifirca Apr 8 '14 at 6:58
7
\$\begingroup\$

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)
\$\endgroup\$
  • 3
    \$\begingroup\$ isSorted xs = and $ zipWith (<=) xs (tail xs) \$\endgroup\$ – Simon Bergot Apr 11 '14 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.