Check a list if sorted in ascending or descending or not sorted in haskell?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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