Check a list if sorted in ascending or descending or not sorted in haskell?
I am new in Haskell. I just studied Haskell for two weeks now. I don't really understand how the if else statement and the list comprehension for haskell works. So I wanted to make function that can figure out the sort type such as the list is sorted in ascending or descending or not sorted at all. I know how to check if the list is sorted ascending and descending but I don't know how to check if the list is not sorted at all.
data SortType = Ascending  Descending  NotSorted deriving (Show)
sorted :: (Ord a) => [a] > TypeOfSort
sorted [] = Ascending
sorted [x] = Ascending
sorted (x:y:xs)  x < y = sorted (y:xs)
 otherwise = Descending
sorted_ = Ascending
It would be a great help if someone could tell me how to do it. Thank you. P/s: this is not a homework/work stuffs but rather something I want to learn.
4 answers

We have an implementation of sort already, from Data.List that we can use to achieve this.
import Data.List (sort) sorted xs  sort xs == xs = Ascending  reverse (sort xs) == xs = Descending  otherwise = NotSorted
If the sorted list is equal to the list, then it must be sorted with an ascended sort.
If the sorted list, reversed, is equal to the list, then it must be sorted with a descended sort.
Otherwise, it's not sorted.
As @BenjaminHodgson points out, the edge conditions might need thinking about. With this implementation, an empty list counts as sorted, so does a list of one item, and so does a list of the same item repeated.
Usage:
λ> sorted [1..5] Ascending λ> sorted [5,4..1] Descending λ> sorted [1,3,1] NotSorted λ> sorted [] Ascending λ> sorted [1] Ascending λ> sorted [1,1,1] Ascending
Alternatively, we can use sortBy for the reverse case, to avoid having to reverse the list completely. This just sorts by the default comparison function, with the arguments flipped, so a less than becomes a greater than.
import Data.List (sort, sortBy) sorted xs  sort xs == xs = Ascending  sortBy (flip compare) xs == xs = Descending  otherwise = NotSorted

My solution without using the sort function and without recursion :
data SortType = Ascending  Descending  NotSorted  Flat  Unknown deriving (Show) sorted :: (Ord a) => [a] > SortType sorted [] = Unknown sorted [a] = Flat sorted xs  and [x == y  (x, y) < zipPairs xs] = Flat  and [x <= y  (x, y) < zipPairs xs] = Ascending  and [x >= y  (x, y) < zipPairs xs] = Descending  otherwise = NotSorted zipPairs :: [a] > [(a, a)] zipPairs xs = zip xs (tail xs)
Faster is probably the one using lambdas
all (\(x, y) > x <= y) (zipPairs xs)
In Python I would probably do something like this
from itertools import izip, islice n = len(lst) all(x <= y for x, y in izip(islice(lst, 0, n  1), islice(lst, 1, n)))

A problematic part of your function is the
 otherwise = Descending
. According to your function definition, if there are two consecutive examples in the list such thatx >= y
, then the function is descending. This is notTrue
: a function is descending if for all two consecutive elementsx > y
(orx >= y
if you do not require it to be strictly descending).Furthermore an additional problem here is that a list with one element (or no elements) can be seen as both
Ascending
andDescending
. So I think the first thing we have to do is define some semantics. We can decide to make the output a list ofTypeOfSort
items, or we can decide to extend the number of options ofTypeOfSort
.In this answer I will pick the last option. We can extend
TypeOfSort
to:data TypeOfSort = Ascending  Descending  Both  NotSorted deriving (Show)
Now we can work on the function itself. The base cases here are of course the empty list
[]
and the list with one element[_]
:sorted [] = Both sorted [_] = Both
Now we need to define the inductive case. When is a list sorted ascendingly? If all elements are (strictly) larger than the previous element. Analogue a list is sorted descending if all elements are (strictly) smaller than the previous element. Let us for now assume strictness. It is easy to alter the function definition later.
So in case we have a list with two or more elements, a list is
Ascending
if the list that starts with the second element isAscending
orBoth
, andx < y
, or in other words:sorted (x:y:xs)  Both < sort_yxs, x < y = Ascending  Ascending < sort_yxs, x < y = Ascending where sort_yxs = sorted (y:xs)
The same holds for descending order: if the rest of the list is in descending order, and the first element is greater than the second, then the list is in descending order:
 Both < sort_yxs, x > y = Descending  Ascending < sort_yxs, > y = Descending where sort_yxs = sorted (y:xs)
In all the remaining cases, it means that some part(s) of the list are
Ascending
and some part(s) areDescending
, so then the list isNotSorted
. otherwise = NotSorted
or putting these all together:
sorted [] = Both sorted [_] = Both sorted (x:y:xs)  Both < sort_yxs, x < y = Ascending  Ascending < sort_yxs, x < y = Ascending  Both < sort_yxs, x > y = Descending  Ascending < sort_yxs, x > y = Descending  otherwise = NotSorted where sort_yxs = sorted (y:xs)
Refactoring: make
TypeOfSort
aMonoid
The above definition contains a lot of edge cases, this makes it hard to write a simple program. We can make it easier by introducing some utility functions. This can for instance be done by defining a function that takes two
TypeOfSort
s and then returns the intersection. Such a function could look like:intersect Both x = x intersect x Both = x intersect Ascending Ascending = Ascending intersect Descending Descending = Descending intersect _ _ = NotSorted
This actually forms a monoid with
Both
as identity element:instance Monoid where mappend Both x = x mappend x Both = x mappend Ascending Ascending = Ascending mappend Descending Descending = Descending mappend _ _ = NotSorted mempty = Both
Now we can rewrite our definition as:
sorted [] = Both sorted [_] = Both sorted (x:y:ys)  x > y = mappend rec Ascending  x < y = mappend rec Descending  otherwise = NotSorted where rec = sorted (y:ys)

I guess you may also do as follows;
data Sorting = Why  Karma  Flat  Descent  Ascent deriving (Show) howSorted :: Ord a => [a] > Sorting howSorted xs  xs == [] = Why  all (== head xs) $ tail xs = Flat  and $ map (uncurry (<=)) ts = Ascent  and $ map (uncurry (>=)) ts = Descent  otherwise = Karma where ts = zip xs $ tail xs