Haskell - 过滤器类型类

Question

有没有一种类型类可以抽象出filter函数？

我在思考这样一个问题：

class Filterable t where
  filter :: (a -> Bool) -> t a -> t a

如果不是这种情况，是否有明确的原因呢？

- marcosh

---

你的思路是相反的。你能想到一个明确的理由，为什么应该有这样一个类吗？考虑一下哪些构造函数（除了[]）需要定义一个实例。 - chepner

看了一下这里，我认为为[]、Set、Seq、Map k、IntMap以及所有建立在它们之上的新类型创建一个Filterable实例是有意义的。 - marcosh

Answer 1

是的，witherable包提供Filterable，还附带了一些常见类型的实例。

- Daniel Wagner

---

非常感谢！但是，对于 Set，它并不是一个函子，因此无法起作用。 - marcosh

Answer 2

Control.Monad 中有一个 mfilter 方法（链接）。

mfilter :: MonadPlus m => (a -> Bool) -> m a -> m a 

- talex

---

谢谢，但t是否真的需要成为Monad来支持过滤操作呢？在我看来，过滤操作应该与Monad无关。 - marcosh

@marcosh 不仅仅是Monad，还有MonadPlus。还有foldMap (\x -> [x | p x]) 或者适用于你的t类型的等价物-- 无论是原样使用，带有Foldable（加上一个“注入器”，例如 pure... ;)），还是具有MonadComprehensions（获得 (Monoid (m b), Foldable t, MonadPlus m) => (b -> Bool) -> t b -> m b）。 - Will Ness

这对我来说实际上非常有趣，我希望会有更多的答案/评论出现... 很明显，你（或许）不能在任意的Functor或Foldable上进行filter - 我想象不出如何过滤任何类型的树（例如当根值未通过谓词测试时，在每个分支上全部通过测试该如何处理？）。但我和你一样惊讶于这需要一个完整的MonadPlus。而且我也并不清楚filter操作通常应遵循哪些规则才配得上这个名字。 - Robin Zigmond

Haskell Wiki在这里提供了一些分析。简而言之，Foldable是关于拆除结构，而Traversable是关于保留结构不变，因此两者都不能让你编写'filter'。 您需要一种结构建立操作，例如'pure'和一些关于'empty'的概念（mzero），这就是为什么'mfilter'有效的原因。 但是您不需要从Applicative或Monad中获得其余结构，并且可以使用'mempty'代替'mzero'：'filter p = foldMap（\a->如果p a则pure a否则mempty）'。 https://wiki.haskell.org/Foldable_and_Traversable#Some_trickier_functions:_concatMap_and_filter - Rein Henrichs

@RobinZigmond 可以独立于 Monad 或 Alternative 或任何其他类型类，开发具有自己规则的 Filterable 类型类。甚至可以拥有逆变的 Filterable 类型构造器。Filterable 函子最简洁的定义是方法 deflate :: f (Maybe a) -> f a，它必须满足适当的身份和组合法则。 - winitzki