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

user_9759263 0
Viewed 77

Source: Hutton, Graham. "Programming in Haskell" (p. 267)

  1. 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)
filter haskell
1 Answers

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.

user_6254030
Related