60

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 :-) )

Micha Wiedenmann
  • 19,979
  • 21
  • 92
  • 137
Prateek
  • 2,377
  • 17
  • 29

3 Answers3

61

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.

Lynn
  • 10,425
  • 43
  • 75
Sjoerd Visscher
  • 11,840
  • 2
  • 47
  • 59
  • 1
    Oh, nice! Didn't even think of that. Wonder if there are any `Foldable` instances in standard-ish libraries that fail to be a `Functor` due to contravariance? – C. A. McCann Dec 02 '11 at 16:44
  • I think you could do it with certain extensions and type synonyms. – PyRulez Dec 05 '13 at 20:42
  • 1
    How about `instance Functor Weird where fmap fn (Weird a aa) = Weird (fn (aa a)) id`? – Nikita Volkov Apr 06 '18 at 13:46
  • 1
    @NikitaVolkov Nice one! But it does not satisfy the functor laws. `fmap id == id` – Sjoerd Visscher Apr 07 '18 at 08:42
  • @SjoerdVisscher depends. Technically speaking `Free` doesn't satisfy the monad laws w.r.t. definitional equality and in the same way `pipes` satisfy appropriate laws only through the `observe` prism. So definitional equality might be not the most sensible/useful/natural one (take quotients e.g. for which definitional equality becomes an annoying artifact of a language you use). Now your `Weird` looks a lot like `Coyoneda`. And your `foldMap` have a very similar and specific semantics: it treats `Weird` as a one-element container and always applies that stored function. – effectfully Apr 07 '18 at 10:09
  • So as soon as you always extract the element from `Weird` as `runWeird (Weird x f) = f x`, the functor laws do hold through the `runWeird` prism. – effectfully Apr 07 '18 at 10:10
54

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!

C. A. McCann
  • 76,893
  • 19
  • 209
  • 302
  • 12
    This is indeed an example of a `Foldable` which cannot be made a `Functor`. However, this seems to be more due to the fact that Haskell's type system cannot express "`Set` makes sense only for `Ord` types, and to make something a `Functor` one only needs to define `fmap` for the types which makes sense, as defined elsewhere", than due to something inherent about what `Set` and `Functor` represent. Thanks for the example, anyway. :-) – Prateek Dec 02 '11 at 18:28
  • 5
    @Prateek: Yes and no. Being fully parametric is very much inherent to what `Functor` represents. That said, a more expressive type system than standard Haskell (including the full type system supported by GHC, actually) could express "fully parametric over some class of types", which is what would be desired here. – C. A. McCann Dec 02 '11 at 18:34
  • 7
    @Prateek: In a more mathematical sense, `Functor` only encompasses specific kinds of functors, from the category of all Haskell types onto a proper subcategory of itself. It can't express functors that operate only on subcategories, or other things that would otherwise make sense. That said, Sjoerd Visscher's example remains both more interesting and more esoteric than mine. :] – C. A. McCann Dec 02 '11 at 18:38
  • 1
    If we are willing to live with `Set` stuff working only for `Ord` types (even though sets in mathematics have no such constraints), we should be willing to tolerate the same imperfection in `Functor` too. – Prateek Dec 02 '11 at 19:56
  • 1
    I'm pretty sure that `Set` doesn't inherently require `Ord` at all times, only when you are "inspecting" it such as by checking the length, displaying it as a string, or getting the minimum / maximum element etc. So if you allowed `Set` to in some situations (e.g `(+) <$> set`) not have `Ord`, and then have it only condense and reorder itself whenever it does have that `Ord` constraint (so yes this cannot be done in standard Haskell, but I'm thinking more from a theoretical/math standpoint). Then you could have `Set` be a true `Functor`, and even an `Applicative` and a `Monad`. – semicolon Jun 29 '16 at 13:39
  • I like this answer, because it provides a reasonable argument against the seemingly reasonable requirement that `Functor` be a superclass of `Foldable`. – chepner Nov 06 '19 at 16:23
27

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.

Lynn
  • 10,425
  • 43
  • 75
Petr
  • 62,528
  • 13
  • 153
  • 317
  • 2
    The Store data type is exactly the free functor over any type constructor, also known as Coyoneda (https://hackage.haskell.org/package/kan-extensions-4.2.3/docs/Data-Functor-Coyoneda.html). – Kris Nuttycombe Oct 19 '15 at 03:53
  • 2
    @KrisNuttycombe Not exactly. `Coyoneda` is existentially quantified where `Store` is not. – Carl Nov 25 '15 at 16:21