Foldable vs Traversable

Question

While studying Applicative deeper, I came to Traversable. Although I already knew Foldable from LYHGG, I haven't seen the former yet, so I started reading the Haskell wiki about Traversable.

While reading it, I understood why Foldable.fold is parallel to Traversable.sequenceA and Foldable.foldMap is parallel to Traversable.traverse.

I've seen also that every Traversable is also a Foldable and a Functor, and sequenceA and traversal have a default implementation in terms of each other:

traverse f = sequenceA . fmap f
sequenceA = traverse id

So, as I have seen in LYHGG that foldMap is a minimal complete definition for Foldable, I thought that, it is parallel to traverse, so fold (which is parallel to sequenceA) would be a minimal complete definition too (which it isn't)... Foldable is not a Functor like Traversable is, so we cannot apply this:

foldMap f = fold . fmap f
fold = foldMap id -- this is ok

Why isn't every Foldable a Functor, and what would be an instance of Foldable that actually isn't a Functor?

Confabulation

Set is a classic example of a Foldable that's not a Functor. So are unboxed vectors. – Hobson

@Hobson I will read more about Set to understand why it isn't a Functor, but, Sets can be thought as containers of things that don't repeat... That being said, I cannot figure out quickly why it is not a Functor instance... – Confabulation

The trouble is that Functor doesn't give implementations the opportunity to constrain their type arguments. Imagine if someone wrote fmap f s where f :: Int -> Integer -> Integer. The type Integer -> Integer is not even an instance of Eq, let alone Ord, so there's no way to check for duplicates when mapping. The function could map multiple elements to identical functions, and you'd have no way of collapsing the duplicates. – Hobson

Unboxed vectors can only contain "unboxable" things, so if xs :: U.Vector Int, fmap Just xs would have to produce something of type U.Vector (Maybe Int), which isn't a real thing. – Hobson

As I understand things, the Traversable class was conceived first (e.g., McBride and Patterson, "Applicative Programming with Effects"; Gibbons and Oliveira, "The Essence of the Iterator Pattern"). Foldable was added as a superclass because of the "containers that aren't Functors" problem. But foldMap falls out of traverse-ing with the Const applicative, as shown in Gibbons and Oliveira's paper. – Kheda

Answer 1

As dfeuer says, Set is a good example of a Foldable that isn't a Functor.

Consider the type of Set.map:

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

Notice that this is almost fmap, but it requires an additional Ord b constraint. Since you have this constraint, it can't be made an instance of Functor.

Note that Set is not a functor on Haskell, even with this restriction. Given cleverly set-up Eq instances we can break the law that fmap f . fmap g === fmap (f . g). See this Stack Overflow question for further discussion.

As noted there, Set is an (endo) functor on the "subcategory of Hask" with ordered types as sets and with order-preserving maps as morphisms.

So even if it isn't apparent, the fact that we can't make Set a functor actually hints at a genuine mathematical issue and not just a limitation of our typeclass machinery.

Ingulf

what I think that is amazing is that mathematically it is a Functor but because of this constraint it cannot be an instance of the Functor typeclass... Don't you think that this resembles an "imperfection" in the language? (The language is really beautiful, concise, and powerful, anyway!) – Confabulation

@Confabulation I edited my answer to describe more context. – Ingulf

I know I should not say "Thank you" in a comment, but really, your explanations were veeeery interesting! :D – Confabulation

The "order-preserving maps as morphisms" thing seems quite restrictive; naively I would think "equality-preserving" would be enough. Can you comment on that a bit? – Zippora

@DanielWagner, I wondered the same thing. Order-preserving gets you efficiency, but I don't see it being absolutely essential. – Hobson

You're probably write that equality preserving is enough. I used order preserving because that's typically how it is presented (can't find a reference off hand) and because its typical to have ordered sets with order preserving maps, so its a more "natural" setting. But I can't think why its actually necessary. – Ingulf

Indeed order-preserving is not necessary. And “equality-preserving” is pretty much a universal requirement, at least when you're talking about actual semantic equalities (== is only a rough approximation to equality; if you use that as a benchmark then tough luck applying the monad laws to anything interesting). Thus, Set is a functor on the ord-constrained Hask category, or indeed a monad on all of Hask if you implement it cleverly. – Malagasy