在Haskell中使用高阶函数实现过滤器

Question

我正在尝试编写一个函数，它接受一个谓词 f 和一个列表，并返回一个由所有满足 f 的项组成的列表，保留原有顺序。技巧在于只使用高阶函数（HoF），不使用递归、推导式和 filter 等。

- dpsthree

Answer 1

你可以用 foldr 来表达 filter：

filter p = foldr (\x xs-> if p x then x:xs else xs) []

- Martijn

Answer 2

显然你是为了学习而来，所以让我给你展示一些很酷的东西。首先，为了复习我们的知识，这种过滤器的类型是：

filter :: (a -> Bool) -> [a] -> [a]

这里最有趣的部分是最后一段 [a] -> [a]。它将一个列表拆分并建立一个新列表。

在Haskell（和其他函数式语言）中，递归模式非常普遍，人们已经为其中一些模式命名了。最简单的是消解和其对偶的生成。我将向您展示如何将其与您的问题联系起来。

不动点

预备知识万岁！ Nothing 的类型是什么？启动 GHCI，它说 Nothing :: Maybe a，我不会反驳。那么 Just Nothing 呢？再次使用 GHCI，它说 Just Nothing :: Maybe (Maybe a)，这也是完全有效的，但是嵌入在任意数量的 Just 中的这个值的类型是什么呢，甚至是无限数量的 Just。即，这个值的类型是什么：

foo = Just foo

Haskell实际上不允许这样的定义，但是稍作调整我们可以定义出这样一个类型：

data Fix a = In { out :: a (Fix a) }

just :: Fix Maybe -> Fix Maybe
just = In . Just

nothing :: Fix Maybe
nothing = In Nothing

foo :: Fix Maybe
foo = just foo

哇，非常接近！使用相同的类型，我们可以创建任意嵌套的nothing：

bar :: Fix Maybe
bar = just (just (just (just nothing)))

顺便说一下: 有人需要皮亚诺算术吗？

fromInt :: Int -> Fix Maybe
fromInt 0 = nothing
fromInt n = just $ fromInt (n - 1)

toInt :: Fix Maybe -> Int
toInt (In Nothing) = 0
toInt (In (Just x)) = 1 + toInt x

这个 Fix Maybe 类型有点无聊。下面是一个其固定点为列表的类型:

data L a r = Nil | Cons a r
type List a = Fix (L a)

这种数据类型将有助于展示一些递归模式。

有用的事实：在Cons a r中，r被称为递归点。

折叠（Catamorphism）

折叠是一种将结构分解的操作。对于列表来说，折叠更为常见。现在可以这样表达折叠的类型：

cata :: (T a -> a) -> Fix T -> a

这可以等价地写成：

cata :: (T a -> a) -> (Fix T -> a)

或者用英语说：

你给我一个将数据类型缩减为值的函数，我会给你一个将它的不动点缩减为值的函数。

实际上，我撒了谎，这个类型真正的定义是：

cata :: Functor T => (T a -> a) -> Fix T -> a

但原则是相同的。请注意，T仅针对递归站点的类型进行参数化，因此Functor部分实际上是在说“给我一种操作所有递归站点的方法”。

然后cata可以定义为：

cata f = f . fmap (cata f) . out

这段内容有些密集，让我详细说明一下。这是一个三步过程：

第一步，我们得到了一个困难的类型Fix t，通过应用out（来自Fix的定义），我们可以使它更容易处理，从而得到一个t (Fix t)。

接下来，我们想将t (Fix t)转换为t a，通过愿景式思考，我们可以使用fmap (cata f)来实现，我们假设我们能够构造出cata。

最后，我们有了一个t a，我们想要一个a，所以我们只需使用f即可。

之前我说过，列表的catamorphism被称为fold，但是目前的cata看起来并不像fold。让我们根据cata来定义一个fold函数。

回顾一下，列表类型是：

data L a r = Nil | Cons a r
type List a = Fix (L a)

这需要成为一个函数对象才能发挥作用，这很简单：

instance Functor (L a) where
  fmap _ Nil = Nil
  fmap f (Cons a r) = Cons a (f r)

因此，专门研究 cata 我们得到：

cata :: (L x a -> a) -> List x -> a

我们已经快要完成了：

construct :: (a -> b -> b) -> b -> L a b -> b
construct _ x (In Nil) = x
construct f _ (In (Cons e n)) = f e n

fold :: (a -> b -> b) -> b -> List a -> b
fold f m = cata (construct f m)

好的，catamorphisms 逐层打破数据结构。

Anamorphisms

列表上的 Anamorphisms 是展开。展开不如它们的 fold 对偶那样常见，它们的类型如下：

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

正如您所看到的，变形构建数据结构。这是更通用的类型：

ana :: Functor a => (a -> t a) -> a -> Fix t

这应该立即看起来很熟悉。定义也让人想起了catamorphism。

ana f = In . fmap (ana f) . f

这只是相反的事情。使用ana构建unfold比使用cata构建fold甚至更简单。请注意Maybe (a, b)和L a b之间的结构相似性。

convert :: Maybe (a, b) -> L a b
convert Nothing = Nil
convert (Just (a, b)) = Cons a b

unfold :: (b -> Maybe (a, b)) -> b -> List a
unfold f = ana (convert . f)

将理论付诸实践

filter函数是一个有趣的函数，它可以从catamorphism或anamorphism构建而来。截至目前为止，其他回答这个问题的答案也使用了catamorphisms，但我会两种方式都定义一下：

filter p = foldr (\x xs -> if p x then x:xs else xs) []

filter p =
  unfoldr (f p)
 where
  f _ [] =
    Nothing
  f p (x:xs) =
    if p x then
      Just (x, xs)
    else
      f p xs

是的，我知道在unfold版本中我使用了递归定义，但请原谅我，我教给你很多理论，而且filter本身就不是递归的。

- dan_waterworth

Answer 3

我认为你可以这样使用 map：

filter' :: (a -> Bool) -> [a] -> [a]
filter' p xs = concat (map (\x -> if (p x) then [x] else []) xs)

你看到了吗？将列表转换为列表的列表，其中如果你想要的元素未通过p，则变为空列表。 filter'(> 1) [1,2,3] 将是：concat [[], [2], [3]] = [2,3] 在prelude中有一个concatMap可以使代码更简单:P

代码应该如下所示：

filter' :: (a -> Bool) -> [a] -> [a]
filter' p xs = concatMap (\x -> if (p x) then [x] else []) xs

使用foldr，如sclv建议的那样，可以用以下方式完成：

filter'' :: (a -> Bool) -> [a] -> [a]
filter'' p xs = foldr (\x y -> if p x then (x:y) else y) [] xs

- Marco

---

有其他的方法可以做到这一点，我在Haskell方面有点新手 :P - Marco

与其使用 concat，你可以更加严格地使用类型，并使用 catMaybes :: [Maybe a] -> [a]。 - dan_waterworth

Answer 4

我建议您看一下foldr函数。

- sclv

Answer 5

好的， ifs 和空列表是允许的吗？

filter = (\f -> (>>= (\x -> if (f x) then return x else [])))

- Marat Salikhov

---

这与我的答案完全相同，只是它使用了列表单子。 还有其他的区别吗？ 而且，这非常不清楚和难以阅读。 - Marco

如果你将 [] 替换为 mzero 并导入 Control.Monad，你就可以在任何单子中使用过滤器，而不仅仅是在列表中。但这并不是 filterM。 - Marat Salikhov

Answer 6

关于整数列表

filter2::(Int->Bool)->[Int]->[Int]
filter2 f []=[]
filter2 f (hd:tl) = if f hd then hd:filter2 f tl
                else filter2 f tl

- Stefan Rosca

---

这个想法是_不要_使用递归。 - Daniel Fischer

Answer 7

我忍不住要用另一种方式回答这个问题，这次完全没有递归。

-- This is a type hack to allow the y combinator to be represented
newtype Mu a = Roll { unroll :: Mu a -> a }
-- This is the y combinator
fix f = (\x -> f ((unroll x) x))(Roll (\x -> f ((unroll x) x)))

filter :: (a -> Bool) -> [a] -> [a]
filter =
  fix filter'
 where
  -- This is essentially a recursive definition of filter
  -- except instead of calling itself, it calls f, a function that's passed in
  filter' _ _ [] = []
  filter' f p (x:xs) =
    if p x then
      (x:f p xs)
    else
      f p xs

- dan_waterworth