2

Considering a type with kind * -> *, I'm trying to find rules and build intuition for when you can and when you cannot have Functor for this type.

So far the rules that I see are the following:

  1. No Functor instance for the container types that have restrictions on the contained values.

Example: You cannot have a Functor instance for Set because Ord is needed for the contained value

  1. No Functor instance for contravariant data types.

Example:

newtype Contra a = Contra (a -> Int)

Besides this, are there other situations?

vidi
  • 2,056
  • 16
  • 34
  • Not a duplicate, but related: http://stackoverflow.com/q/7220436/477476 – Cactus Apr 25 '17 at 09:18
  • Why not formulate it constructively: what are the situations when you _can_ have a Functor instance? That's IMO always so much more useful to consider. – leftaroundabout Apr 25 '17 at 09:21
  • 1
    I suppose you could count types with the wrong kind, e.g. `newtype Fix f = Fix { unFix :: f (Fix f) }` has a kind `Fix :: (* -> *) -> *` whereas `Functor` requires a type constructor of kind `* -> *`, i.e. `Functor :: (* -> *) -> Constraint`. (`Fix` is, however, a functor in the general categorical sense, from the category of Haskell endofunctors to the category of Haskell types.) – Benjamin Hodgson Apr 25 '17 at 09:43
  • @leftaroundabout I'm looking for some rules plus the intuition behind them. At some point I thought that you could have functors for any container, which is obviously wrong. So I have the feeling that you can have Functor instances for most of the containers except a few cases. – vidi Apr 25 '17 at 09:47
  • @cactus I've seen the linked question but I'm trying to identify other rules and build an intuition – vidi Apr 25 '17 at 09:52
  • @BenjaminHodgson Wrong kind is definitely not suitable for Functor. I'll update the question to avoid discussions in this direction. As for your Fix type I don't understand it. Can you post a link with more info? Thanks! – vidi Apr 25 '17 at 09:56

3 Answers3

5

In addition to your rules:

  • Must be of kind * -> *
  • No Functor instance for the container types that have restrictions on the contained values.
  • No Functor instance for contravariant data types.

I would add a few:

  • A natural extension of "not for contravariant types": no Functor instance for invariant data types. e.g. data Iso a b = Iso (a -> b) (b -> a)

  • GADTs often cannot have a Functor instance. For example,

    data Foo a where
    Foo :: Foo Int

    Perhaps you would somehow want to lump this into the "only covariant" rule somehow (it's not clear to me what variance this even has), or the "unrestricted container types" rule somehow (GADTs introduce type equalities that are very constraint-like).

However, keep in mind that these rules apply to Functor only, not to functors in general. I expect any stupid type (of appropriate kind) you can cook up will be a functor on some suitable category closely related to Hask.

Daniel Wagner
  • 145,880
  • 9
  • 220
  • 380
  • Can you explain with more details what you mean by "these rules apply to Functor only, not to functors in general."? Thanks! – vidi Apr 25 '17 at 15:31
  • 1
    @vidi Expanding on that might be another whole answer, and the level to write it at depends a lot on how comfortable you are with functors to begin with. But in short: you could imagine `class Functor' f where fmap' :: Ord b => (a -> b) -> f a -> f b` with essentially the same class laws as `Functor` and which would admit an instance for `Set` even though `Functor` doesn't. And a suitably modified class with an essentially identical class law could be cooked up for most non-`Functor`s. – Daniel Wagner Apr 25 '17 at 18:26
  • 1
    @vidi Or, to put it another way: the strictures of Haskell as a language already make it quite easy to satisfy the much more relaxed rules imposed by merely being a functor. Parametric polymorphism already stops you from writing most of the stupid stuff that the functor laws are designed to rule out. – Daniel Wagner Apr 25 '17 at 18:28
5

From the point of view of category theory, Haskell's type constructors of the kind *->* define a mapping of objects in the category Hask (it's a category modulo termination issues, which I'm going to conveniently ignore). A functor is a mapping of objects and, more importantly, a mapping of morphisms. In fact, it's primarily a mapping of morphisms--the mapping of objects is, in a way, a side effect of that. Objects are just the endpoints of morphisms. This mapping of morphisms must preserve composition and identity.

In Haskell, morphisms are functions, and the mapping of functions is implemented as fmap.

The fact that in Haskell we start with the mapping of objects is a little backwards. This works because the syntax of the language drastically limits the possibilities for defining the mapping of objects. Such mapping are very regular and, quite often, come equipped with canonical mappings of functions. For instance, algebraic data types are constructed using products and coproducts, which are functorial in nature (hence the possibility of deriving Functor automatically). Also, function types (categorical exponentials) are functorial in the second argument (and contravariant in the first). So, as long as we use the tools of the bicartesian closed category (products, coproducts, and exponentials), it's easy to construct functorial mappings of objects.

A functor must be defined for every object in a given category, so data types that are constrained by type classes (e.g., Set with the Ord constraint) are not Functors in Hask, but they may be functors in a subcategory of Hask. (It's possible to define subcategories in Haskell together with their own functors.)

Bartosz Milewski
  • 11,012
  • 5
  • 36
  • 45
0

There is -XDerivingFunctor extension in Haskell user guide. You can find full description here. It has description of all cases when functor deriving can fail. This description has cases when algorithm checks for proper kind, etc. But I believe this list of constraints for algorithm is exhaustive.

For example, another case, when type has kind * -> * but cannot be instance of Functor:

A data type’s last type variable is used in an -XExistentialQuantification constraint, or is refined in a GADT

Shersh
  • 9,019
  • 3
  • 33
  • 61
  • 2
    According to the documentation, `DerivingFunctor` won't derive a functor instance for `newtype Wrong a = Wrong (Either a Int)`; but that doesn't mean `Wrong` *can't* be a `Functor`. – Daniel Wagner Apr 25 '17 at 12:34
  • @DanielWagner Yes, it's true. `DerivingFunctor` mechanism is more restrictive. I was just referring to official documentation where one can look for all cases. But this documentation should be read not blindly to not miss that case you mentioned in comment. – Shersh Apr 25 '17 at 12:37