Checking whether the list is ordered according to the function

Question

How can I check whether the list is ordered according to the function?

> ordered (<) [1,2,3,4,5]
True
> ordered (<) [5,4,3,2,1]
False
> ordered (>) [5,4,3,2,1]
True

I tried to write something like this, but it doesn't work - what's wrong in this code?

ordered :: (Ord a) => (a -> a -> Bool) -> [Integer] -> Bool
ordered f [] = True
ordered f [a] = True
ordered f (x1:x2:xs) =
    if ((f) x1 x2)
        then ordered f [x2]++xs
        else False

Answer 1

The errors you get are twofold - first error

$ > ghci tmp.hs
GHCi, version 7.10.3: http://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling Main             ( tmp.hs, interpreted )

tmp.hs:8:14:
    Couldn't match expected type ‘[Integer]’ with actual type ‘Bool’
    In the first argument of ‘(++)’, namely ‘ordered f [x2]’
    In the expression: ordered f [x2] ++ xs

tmp.hs:8:14:
    Couldn't match expected type ‘Bool’ with actual type ‘[Integer]’
    In the expression: ordered f [x2] ++ xs
    In the expression:
      if ((f) x1 x2) then ordered f [x2] ++ xs else False
    In an equation for ‘ordered’:
        ordered f (x1 : x2 : xs)
          = if ((f) x1 x2) then ordered f [x2] ++ xs else False
Failed, modules loaded: none.

says essentially that you try to apply the (++) operator to two different lists - because ordered f [x2] :: [Bool] and xs :: [Integer]

to fix it - you simply need to add braces ordered f ([x2] ++ xs)

compiling this you get another error

$ >  ghci tmp.hs
GHCi, version 7.10.3: http://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling Main             ( tmp.hs, interpreted )

tmp.hs:7:13:
    Couldn't match expected type ‘a’ with actual type ‘Integer’
      ‘a’ is a rigid type variable bound by
          the type signature for
            ordered :: Ord a => (a -> a -> Bool) -> [Integer] -> Bool
          at tmp.hs:3:12
    Relevant bindings include
      f :: a -> a -> Bool (bound at tmp.hs:6:9)
      ordered :: (a -> a -> Bool) -> [Integer] -> Bool
        (bound at tmp.hs:4:1)
    In the first argument of ‘f’, namely ‘x1’
    In the expression: ((f) x1 x2)
Failed, modules loaded: none.

which says that ghc cannot match any Ord a with the concrete type Integer.

The fix is to change the type signature - to the following

ordered :: Ord a => (a -> a -> Bool) -> [a] -> Bool

---

On a side note - the algorithm can be simplified using the functions

• and
• zipWith
• tail

ordered f xs = and $ zipWith f xs (tail xs)

Answer 2

With list comprehensions, it can be

ordered f xs = null [() | (a,b) <- zip xs (drop 1 xs), not (f a b)]

This can of course be coded with any, and, etc., if you're familiar with them. With list comprehensions you can just wing it, while you're still learning.

Your code is also good, it just misses some parentheses. It should be

       then ordered f ( [x2]++xs )

Incidentally, just saying

doesn't work - what's wrong in this code?

is not enough. Surely you've tried to load this code, and have received an error message, talking something about "type mismatch", even showing you the expression in question,

    In the expression: ordered f [x2] ++ xs
    In the expression:
      if ((f) x1 x2) then ordered f [x2] ++ xs else False
    In an equation for `ordered':
        ordered f (x1 : x2 : xs)
          = if ((f) x1 x2) then ordered f [x2] ++ xs else False

which could have provided a clue. In Haskell, function application (denoted by just juxtaposition, i.e. white space) is of highest precedence, so your code was interpreted as (ordered f [x2]) ++ (xs).