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

Question

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

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 功能不够强大，无法实现保留容器形状的过滤操作。我经常将 Foldable 视为“您可以制作成列表的任何东西”。值得注意的是，这并不意味着您可以将列表恢复为特定的可折叠类型。因此，这个 filterF 只能 return [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，但您实际上不能保证：您使用 different 类型，它必须是 Monoid 和 Applicative 但不需要是 Foldable，以建立 return 值。

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

Defining a filterF function that can be used with any Foldable type

haskell

filter