An example of a Foldable which is not a Functor (o

Question

A Foldable instance is likely to be some sort of container, and so is likely to be a Functor as well. Indeed, this says

A Foldable type is also a container (although the class does not technically require Functor, interesting Foldables are all Functors).

So is there an example of a Foldable which is not naturally a Functor or a Traversable? (which perhaps the Haskell wiki page missed :-) )

Answer 1

Reading Beautiful folding I realized that any Foldable can be made a Functor by wrapping it into

data Store f a b = Store (f a) (a -> b)

with a simple smart contructor:

store :: f a -> Store f a a
store x = Store x id

(This is just a variant of the Store comonad data type.)

Now we can define

instance Functor (Store f a) where
    fmap f (Store x g)   = Store x (f . g)

instance (F.Foldable f) => F.Foldable (Store f a) where
    foldr f z (Store x g)    = F.foldr (f . g) z x

This way, we can make both Data.Set.Set and Sjoerd Visscher's Weird a functor. (However, since the structure doesn't memoize its values, repeatedly folding over it could be very inefficient, if the function that we used in fmap is complex.)

---

Update: This also provides an example of a structure that is a functor, foldable but not traversable. To make Store traversable, we would need to make (->) r traversable. So we'd need to implement

sequenceA :: Applicative f => (r -> (f a)) -> f (r -> a)

Let's take Either b for f. Then we'd need to implement

sequenceA' :: (r -> Either b a) -> Either b (r -> a)

Clearly, there is no such function (you can verify with Djinn). So we can neither realize sequenceA.

Answer 2

Here's an easy example: Data.Set.Set. See for yourself.

The reason for this should be apparent if you examine the types of the specialized fold and map functions defined for Set:

foldr :: (a -> b -> b) -> b -> Set a -> b

map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b

Because the data structure relies on a binary search tree internally, an Ord constraint is needed for elements. Functor instances must allow any element type, so that's not viable, alas.

Folding, on the other hand, always destroys the tree to produce the summary value, so there's no need to sort the intermediate results of the fold. Even if the fold is actually building a new Set, the responsibility for satisfying the Ord constraint lies on the accumulation function passed to the fold, not the fold itself.

The same will probably apply to any container type that's not fully parametric. And given the utility of Data.Set, this makes the remark you quoted about "interesting" Foldables seem a bit suspect, I think!

Answer 3

Here's a fully parametric example:

data Weird a = Weird a (a -> a)

instance Foldable Weird where
  foldMap f (Weird a b) = f $ b a

Weird is not a Functor because a occurs in a negative position.