haskell - 以 lambda 演算的方式理解 Haskell 函数

Question

我试图定义过滤器功能。根据函数的定义，过滤器函数是一个函数（比如帮助函数与主过滤器函数不同），它接受一个函数和一个列表来给出一个列表。帮助函数接受一个变量并返回一个 Bool 值。但是根据第 4 行，帮助函数评估 a 和 [x] 以给出一个 Bool 值，然后最终返回一个列表。

那么我可以将帮助函数理解为一个接受 a 和 [a] 以给出 Bool 值的函数。然后主过滤器函数接受这个 Bool 值来返回一个列表？

我知道函数的定义并没有暗示这一点，但它基于代码有点合乎逻辑。谢谢

filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' a (x:xs)
  | a x == True = x:filter' a xs
  | otherwise = filter' a xs

标签： haskellhigher-order-functions

Answer 1

您可以更多地使用语法来帮助您理解：

filter' :: (a -> Bool) -> [a] -> [a]
filter' p [] = []
filter' p (x:xs)
     | (p  x) == True   = x : ( filter' p xs )
     | otherwise        =     ( filter' p xs )

哪个是

filter' :: (a -> Bool) -> [a] -> [a]
filter' p [] = []
filter' p (x:xs)
     | (p  x)     = x : ( filter' p xs )
     | otherwise  =     ( filter' p xs )

或者把它翻译成更基本的结构，

filter' :: (a -> Bool) 
          ->   [a] -> [a]
filter' p = ( \ xs -> case xs of 
             {  []            ->  []
             ;  (x:ys) | p x  ->  x : ( filter' p ys )
             ;  (x:ys)        ->      ( filter' p ys )  } )

“ p”代表“谓词”。它用于filter'测试x输入中的每个，根据测试产生的 ean 值xs决定是否将其包含x在输出中。Bool

p只是从一个调用filter'到下一个调用不变地传递。这通常用所谓的“worker-wrapper”转换编码掉，

filter' :: (a -> Bool) -> [a] -> [a]
filter' p xs = go xs where
   go [] = []
   go (x:xs) | p x   = x : go xs
             | otherwise = go xs

最后，一个看起来更简单的定义也可以是

filter' :: (a -> Bool) -> [a] -> [a]
filter' p xs = go xs where
   go []     = []
   go (x:xs) = [x | p x] ++ go xs

这与foldMap基于 - 的定义很好地对应

filter' p = foldMap (\ x -> [x | p x])