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

  • answered 2017-11-12 19:53 Zpalmtree

    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
    

  • answered 2017-11-12 19:54 Elmex80s

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

  • answered 2017-11-12 19:58 Willem Van Onsem

    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)
    

  • answered 2017-11-12 21:51 Redu

    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