改进我的haskell过滤器实现

整理实现的最简单方法是使用 guards . 而不是 pattern = value ,你可以写 pattern | boolean = value ;只有在 boolean 是真的。因此,我们可以

filter1 :: (a -> Bool) -> [a] -> [a]
filter1 p (x:xs) | p x       = x : filter1 p xs
                 | otherwise = filter1 p xs
filter1 _ []                 = []

(注意 otherwise 只是 True )现在,我们有了 filter p xs 在两个地方,所以我们可以把它移到 where 所有共享一个共同模式的事物都可以共享这些规则,即使它有不同的保护:

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

(此实现是 used by GHCs Prelude )

现在,它们都不是尾递归的。这可能是不利的,但它确实使功能变得懒惰。如果我们想要一个尾部递归版本,我们可以编写

filter3 :: (a -> Bool) -> [a] -> [a]
filter3 p xs = let filter3' p (x:xs) ys | p x       = next $! x:ys
                                        | otherwise = next $! ys
                     where next = filter3' p xs
                   filter3' _ []     ys             = reverse ys
               in filter3' p xs []

但是,请注意,由于 reverse ,所以我们严格要求 $! . (我认为我做得对,我可能强迫错误的变量。不过,我想我做得对。)

这些实现看起来都像您的。当然,还有其他的。一是基于 foldr :

filter4 :: (a -> Bool) -> [a] -> [a]
filter4 p = let check x | p x       = (x :)
                        | otherwise = id
            in foldr check []

我们利用这里的无点风格;因为 xs 将是双方最后的争论 filter4 和 foldr check [] ,我们可以省略它,同样的还有 check .

您还可以利用以下列表:

import Control.Monad
filter5 :: MonadPlus m => (a -> Bool) -> m a -> m a
filter5 p xs = do x <- xs
                  guard $ p x
                  return x

列表monad表示不确定性。你选择一个元素 x 从 XS ,确保它满足 p ,如果有则返回。然后将所有这些结果收集在一起。但请注意,这现在更为普遍;这适用于任何 MonadPlus (一个单子,也是一个单子;也就是说,它有一个结合的二元运算 mplus 艾斯 ++ 对于列表和标识元素 mzero 艾斯 [] 对于列表),例如 [] 或 Maybe . 例如, filter5 even $ Just 1 == Nothing 和 filter5 even $ Just 2 == Just 2 .

我们也可以调整 福尔德尔 -基于版本获取不同的通用类型签名:

import Control.Monad
import qualified Data.Foldable as F
import qualified Data.Monoid   as M
filter6 :: (F.Foldable f, MonadPlus m, M.Monoid (m a))
        => (a -> Bool) -> f a -> m a
filter6 p = let check x | p x       = return x
                        | otherwise = mzero
            in F.foldMap check

这个 Data.Foldable module 提供 Foldable 类型类,它表示可以 fold 像一个列表一样(将结果放在一个泛型中 Monoid 相反) filter 需要一个 莫纳德普拉斯 对结果也有限制,以便我们可以 return x . 这个 foldMap 函数需要将所有内容转换为 幺半群 ,然后将它们连接在一起。两者之间的不匹配 f a 在左边和 m a 右边的意思是你可以,例如, filter6 一 也许吧 把清单拿回来。

我肯定有(很多!)其他实施 滤波器 但这是我能相对快速想到的6个。现在,我最喜欢哪一个呢?在直截了当的 filter2 以及 福尔德尔 基于 过滤器4 . 和 filter5 对于它的泛型类型签名是很好的。(我不认为我需要像 过滤器6 事实上 滤光器2 GHC使用的是一个优点,但GHC也使用一些时髦的重写规则,所以我不清楚没有这些规则它是优越的。我个人会的 可能 一起去 过滤器4 (或) 过滤器5 如果我需要遗传的话),但是 滤光器2 很好。

对清单的理解如何?

myfilter f xs = [x | x <- xs, f x]

你至少可以抽出那根普通的干掉一点。 myfilter f xs 代码:

myfilter :: (a -> Bool) -> [a] -> [a]
myfilter f (x:xs) = if f x
    then x : rest
    else rest
        where rest = myfilter f xs
myfilter _ [] = []

对比一下,这里是维基百科的实现:

myfilter :: (a -> Bool) -> [a] -> [a]
myfilter _ []                 = []
myfilter f (x:xs) | f x       = x : myfilter f xs
                  | otherwise = myfilter f xs

在哈斯克尔,大部分时间你可以(也应该)使用 guards 而不是if-then-else:

myfilter :: (a -> Bool) -> [a] -> [a]
myfilter f (x:xs)
   | f x       = x : myfilter f xs
   | otherwise = myfilter f xs
myfilter _ [] = []

这最终是基本上相同的定义使用 in the standard library .