检查列表是否按功能排序

Question

如何根据功能检查列表是否已订购？

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

我试着写这样的东西,但它不起作用 - 这段代码有什么问题？

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

你得到的错误是双重的 - 第一个错误

$ > 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.

基本上你说你试图将(++)运算符应用于两个不同的列表 - 因为ordered f [x2] :: [Bool]和xs :: [Integer]

修复它 - 你只需要添加大括号 ordered f ([x2] ++ xs)

编译这个你得到另一个错误

$ >  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.

这说ghc Ord a与具体类型不匹配Integer.

修复方法是将类型签名更改为以下内容

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

另一方面 - 使用这些功能可以简化算法

• and
• zipWith
• tail

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