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.
λ> sorted [1..5] Ascending λ> sorted [5,4..1] Descending λ> sorted [1,3,1] NotSorted λ> sorted  Ascending λ> sorted  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 >= yif 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
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
TypeOfSortitems, or we can decide to extend the number of options of
In this answer I will pick the last option. We can extend
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
Ascendingif the list that starts with the second element is
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
Ascendingand some part(s) are
Descending, so then the list is
| 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)
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
TypeOfSorts 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
Bothas 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