Case study – Sortedness
We now perform a small case study designing an algorithm to check whether a collection is sorted.
Sorted lists
The more directed definition for checking whether a list is sorted makes use of explicit recursion and distinguishes three cases:
sorted :: Ord a => [a] -> Bool sorted [] = True sorted [x] = True sorted (x:y:zs) = x <= y && sorted (y:zs)
Empty and one-element lists are always sorted. A two-or-more-element list is sorted if the first two elements are in ascending order and if the tail is sorted.
We would like to carry this definition over to other Foldable collections. Unfortunately, it does not fit the structurally recursive pattern of foldr or foldMap that is supported by other foldables. The reason is that the definition distinguishes the one-element list from other non-empty lists.