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

Question

资料来源:格雷厄姆·赫顿。 “Haskell 编程”(第 267 页)

5. Using foldMap, define a generic version of the higher-order function filter on lists that can be used with any foldable type:

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

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

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

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

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，但您实际上不能 promise :您使用不同类型，该类型必须是 Monoid 和 Applicative，但不需要是 Foldable ，建立返回值。