Monday 6 June 2016

Haskell: Check whether list is sorted or not.


SortUtil.hs
<
module SortUtil where
    isSorted :: (Ord a) => [a] -> Bool
    isSorted [] = True
    isSorted (x:[]) = True
    isSorted (x: y: xs) = if (x <= y) then checkAscending (y:xs) else checkDescending (y:xs)

    checkAscending :: (Ord a) => [a] -> Bool
    checkAscending [] = True
    checkAscending (x : []) = True
    checkAscending (x:y:xs) = (x <= y) && checkAscending (y:xs)

    checkDescending :: (Ord a) => [a] -> Bool
    checkDescending [] = True
    checkDescending (x : []) = True
    checkDescending (x:y:xs) = (x >= y) && checkDescending (y:xs)

*SortUtil> :load SortUtil.hs
[1 of 1] Compiling SortUtil         ( SortUtil.hs, interpreted )
Ok, modules loaded: SortUtil.
*SortUtil> 
*SortUtil> isSorted [12, 3]
True
*SortUtil> isSorted [12, 15]
True
*SortUtil> isSorted [7, 5, 3, 2, 10]
False
*SortUtil> isSorted [7, 5, 3, 2]
True
*SortUtil> isSorted [2, 3, 5, 7, 0]
False
*SortUtil> isSorted [2, 3, 5, 7]
True

We can rewrite above logic using As pattern like below.


SortUtil.hs
{-# LANGUAGE BangPatterns #-}

module SortUtil where
    isSorted :: (Ord a) => [a] -> Bool
    isSorted [] = True
    isSorted (x:[]) = True
    isSorted (x: rest@(y: _)) = if (x <= y) then checkAscending rest else checkDescending rest

    checkAscending :: (Ord a) => [a] -> Bool
    checkAscending [] = True
    checkAscending (x : []) = True
    checkAscending (x: rest@(y:xs)) = (x <= y) && checkAscending rest

    checkDescending :: (Ord a) => [a] -> Bool
    checkDescending [] = True
    checkDescending (x : []) = True
    checkDescending (x: rest@(y:xs)) = (x >= y) && checkDescending rest



Previous                                                 Next                                                 Home

No comments:

Post a Comment