# 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.

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 @Benjamin-Hodgson 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 that `x >= y`, then the function is descending. This is not `True`: a function is descending if for all two consecutive elements `x > y` (or `x >= 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` and `Descending`. So I think the first thing we have to do is define some semantics. We can decide to make the output a list of `TypeOfSort` items, or we can decide to extend the number of options of `TypeOfSort`.

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 is `Ascending` or `Both`, and `x < 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) are `Descending`, so then the list is `NotSorted`.

``````                | 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` a `Monoid`

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

``````data Sorting = Why | Karma | Flat | Descent | Ascent deriving (Show)