定义可与任何 Foldable 类型一起使用的 filterF 函数

Question

资料来源：格雷厄姆·赫顿。“ Haskell 编程”（第 267 页）

5. 使用foldMap，在可与任何可折叠类型一起使用的列表上定义高阶函数过滤器的通用版本：

filterF :: Foldable t => (a -> Bool) -> t a -> [a]

我正在做这个练习并有一些问题：

• 是不是正确的类型filterF :: Foldable t => (a -> Bool) -> t a -> t a？过滤器不是应该保留容器的结构吗？

这是我的尝试；这是对的吗 ？我应该限制Monoid吗t？

filterF :: Foldable t => (a -> Bool) -> t a -> t a
filterF p = foldMap (\x -> if p x then pure x else mempty)

Answer 1

Foldable 的功能不够强大，无法实现保留容器形状的过滤操作。我经常将可折叠视为“可以放入列表的任何东西”。值得注意的是，这并不意味着您可以将列表重新设置为特定的可折叠类型。因此，这个filterF只能返回[a]。

您的实现很好，但与您的类型签名不匹配。向 GHCI 询问类型，您会发现：

> :t filterF
filterF
  :: (Foldable t, Monoid (f a), Applicative f) =>
     (a -> Bool) -> t a -> f a

这可以专门针对本书要求的类型（Foldable t => (a -> Bool) -> t a -> [a]），但不是您认为该操作应该具有的类型（Foldable t => (a -> Bool) -> t a -> t a）。特别是，您声明了这一点t ~ f，但您实际上不能承诺：您使用不同的类型（必须是 Monoid 和 Applicative 但不必是 Foldable）来构建返回值。