Source: Hutton, Graham. "Programming in Haskell" (p. 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]
I am doing this exercise and have some questions:
- Isn't the correct type
filterF :: Foldable t => (a -> Bool) -> t a -> t a? Isn't filter supposed to preserve the structure of the container ?
This is my attempt; is it correct ? Should I place a Monoid restriction on t ?
filterF :: Foldable t => (a -> Bool) -> t a -> t a
filterF p = foldMap (\x -> if p x then pure x else mempty)
CodePudding user response：
Foldable is not powerful enough to implement a filter operation that preserves the shape of the container. I often think of Foldable as "anything you could make into a list". Notably this does not mean you could make a list back into a specific Foldable type. Thus, this filterF can only return [a].
Your implementation is fine, but doesn't match your type signature. Ask GHCI for the type, and you will find:
> :t filterF
filterF
:: (Foldable t, Monoid (f a), Applicative f) =>
(a -> Bool) -> t a -> f a
This can be specialized to the type that the book asks for (Foldable t => (a -> Bool) -> t a -> [a]), but not to the type you think this operation should have (Foldable t => (a -> Bool) -> t a -> t a). In particular, you claim that t ~ f, but you can't actually promise that: you use a different type, which must be Monoid and Applicative but need not be Foldable, to build up the return value.