<= 和 > 运算符作为函数参数

Question

快速排序：

-- First variant:
qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (x:xs) = left x ++ [x] ++ right x 
  where left  n = qsort [m | m <- xs, m <= n]
        right n = qsort [m | m <- xs, m  > n]

-- λ: qsort [10,2,5,3,1,6,7,4,2,3,4,8,9]
-- [1,2,2,3,3,4,4,5,6,7,8,9,10]

我看到 left 和 right 函数几乎相同。因此我想把它重写得更短一些……类似的东西：

-- Second variant:
qsort' :: (Ord a) => [a] -> [a]
qsort' [] = []
qsort' (x:xs) = (srt <=) ++ [x] ++ (srt >)
  where srt f = qsort' [m | m <- xs, m f x]

但是当我尝试将其加载到 ghci:

时出现错误

λ: :load temp
[1 of 1] Compiling Main             ( temp.hs, interpreted )

temp.hs:34:18:
    Couldn't match expected type `[a]'
                with actual type `(t0 -> [a]) -> Bool'
    Relevant bindings include
      srt :: forall t. t -> [a] (bound at temp.hs:35:9)
      xs :: [a] (bound at temp.hs:34:11)
      x :: a (bound at temp.hs:34:9)
      qsort' :: [a] -> [a] (bound at temp.hs:33:1)
    In the first argument of `(++)', namely `(srt <=)'
    In the expression: (srt <=) ++ [x] ++ (srt >)
    In an equation for qsort':
        qsort' (x : xs)
          = (srt <=) ++ [x] ++ (srt >)
          where
              srt f = qsort' [m | m <- xs, m f x]

temp.hs:34:37:
    Couldn't match expected type `[a]'
                with actual type `(t1 -> [a]) -> Bool'
    Relevant bindings include
      srt :: forall t. t -> [a] (bound at temp.hs:35:9)
      xs :: [a] (bound at temp.hs:34:11)
      x :: a (bound at temp.hs:34:9)
      qsort' :: [a] -> [a] (bound at temp.hs:33:1)
    In the second argument of `(++)', namely `(srt >)'
    In the second argument of `(++)', namely `[x] ++ (srt >)'
    In the expression: (srt <=) ++ [x] ++ (srt >)

temp.hs:35:38:
    Could not deduce (a ~ (t -> a -> Bool))
    from the context (Ord a)
      bound by the type signature for qsort' :: Ord a => [a] -> [a]
      at temp.hs:32:11-31
      `a' is a rigid type variable bound by
          the type signature for qsort' :: Ord a => [a] -> [a]
          at temp.hs:32:11
    Relevant bindings include
      m :: a (bound at temp.hs:35:29)
      f :: t (bound at temp.hs:35:13)
      srt :: t -> [a] (bound at temp.hs:35:9)
      xs :: [a] (bound at temp.hs:34:11)
      x :: a (bound at temp.hs:34:9)
      qsort' :: [a] -> [a] (bound at temp.hs:33:1)
    The function `m' is applied to two arguments,
    but its type `a' has none
    In the expression: m f x
    In a stmt of a list comprehension: m f x
Failed, modules loaded: none.
λ:

我阅读了错误信息，但我仍然不明白原因...

Answer 1

你不应该使用 f 作为中缀。可以把f放在前面，用括号表示函数(<=):

来解决

-- third variant:
qsort' :: (Ord a) => [a] -> [a]
qsort' [] = []
qsort' (x:xs) = (srt (<=)) ++ [x] ++ (srt (>))
  where srt f = qsort' [m | m <- xs, f m x]

这主要是因为你基本上想做的是在m和x上调用f。现在默认的 lambda 演算总是首先计算左边列出的函数。

Haskell 只是为运算符提供了一些语法糖：当你写 a+b 时，你基本上写的是 (+) a b （在幕后）。这是 Haskell 最喜欢的，但是编译器因此提供了一些方便程序员的功能。因为写 a*b+c*d 比写 (+) ((*) a b) ((*) c d) 容易得多，但第二个实际上是如何在 lambda-calculus 中写这样的东西。

为了将运算符视为函数，您将它们写在方括号中，因此要获得 <= 的函数变体，您可以编写 (<=).

编辑

正如@Jubobs 所说，您也可以使用中缀，但因此需要您使用反引号：

-- fourth variant:
qsort' :: (Ord a) => [a] -> [a]
qsort' [] = []
qsort' (x:xs) = (srt (<=)) ++ [x] ++ (srt (>))
  where srt f = qsort' [m | m <- xs, m `f` x]

问题主要是你需要通过f传递你的函数，而<=和>不是函数，(<=) 和 (>) 是。从技术上讲，故事有点复杂，但我想学习基础知识就足够了。

通过使用反引号，Haskell 读取：

x `f` y

如：

f x y

（请注意，这并不完全正确，因为运算符也具有 优先级 ：* 比 + 绑定更紧密，但这些更 "details" 的过程）。

将括号放在运算符上会产生相反的效果：

x o y

是

(o) x y

有 o 个操作员。

<= 和 > 运算符作为函数参数

The <= and > operators as a function arguments

haskell