改进我的Haskell Filter实现

Question

我最近一直在教自己Haskell,我的一个练习就是重新实现这个filter功能.然而,在我演过的所有练习中,我对这个练习的答案在我看来是最丑陋和最长的.我怎么能改进它？有什么Haskell技巧我还不知道吗？

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

谢谢

Answer 1

结合实施的最简单方法是使用警卫.而不是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 _ []                 = []

(此实施是GHC 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 [],我们就可以用的最后一个参数它的Elid,同样check.

您还可以利用列表monad:

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(monad也是一个monoid;也就是说,它具有关联二进制操作mplus- ++用于列表 - 和一个标识元素mzero- []用于列表),例如[]或Maybe.例如filter5 even $ Just 1 == Nothing,和filter5 even $ Just 2 == Just 2.

我们还可以调整foldr基于版本的版本以获得不同的泛型类型签名:

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模块提供Foldable类型的类,其表示可以被任何结构fold编像列表(把结果放置在一个通用的Monoid,而不是.)我们filter需要MonadPlus对结果约束以及使我们可以写return x.该foldMap函数需要一个函数将一切转换为a的元素Monoid,然后将它们连接在一起.f a左侧和m a右侧之间的不匹配意味着您可以,例如,filter6a Maybe并返回一个列表.

我确信有(很多!)其他实现filter,但这些是我能想到的相对较快的6.现在,我最喜欢哪一个呢？这是直截了当filter2和foldr基础之间的折腾filter4.并且filter5它的通用类型签名很好用.(我认为我不需要像filter6's 那样的类型签名.)filter2GHC使用的事实是一个优点,但GHC也使用了一些时髦的重写规则,所以对我而言,如果没有这些规则,它是优越的并不明显.就个人而言,我可能会filter4(或者filter5如果我需要通用性),但filter2绝对没问题.

Answer 2

列表理解怎么样？

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