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

Andrey Bushman 发表于 Dev

安德烈·布什曼

快速排序：

-- 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.
λ:

我阅读了错误消息，但仍然不理解原因...

威廉·范昂塞姆

您不应该将其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]

这主要是因为你基本上想要做的是电话 f上m和x。现在，默认的lambda-calculus始终首先评估左侧列出的函数。

Haskell只为操作员提供了一些语法上的便利：当您编写时a+b，您基本上写的是(+) a b（在幕后）。这是Haskell最喜欢的，但是编译器因此提供了一些功能以方便程序员。由于编写a*b+c*d比编写要容易得多(+) ((*) a b) ((*) c d)，但是第二个实际上是如何在lambda微积分中编写这样的东西。

为了看到运营商的功能，你写他们括号，因此要获得的功能变的<=，你写的(<=)。

编辑

正如@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，并且<=和>不是函数，(<=)和(>)是。从技术上讲，这个故事要复杂一些，但是我想这在学习基础知识时就足够了。