how do you determine if a type is a functor or not in haskell?

Question

I have a data type:

data Tree a = Leaf | Branch a (Tree a) (Tree a)

I want to determine, and not just for this data type, but for others such as String, if these data types are law-abiding instances of functor (https://hackage.haskell.org/package/base-4.14.0.0/docs/Data-Functor.html). The link indicates that you can prove a type is a functor if it has a function fmap, which, given any types a and b, lets you apply any function of type (a -> b) to turn an f a into an f b, preserving the structure of f. How would I test this for my Tree data type, or String data type?

Answer 1

Short non-answer

Before you do any thinking yourself, try to let GHC write the instance for you:

{-# LANGUAGE DeriveFunctor #-}

data Tree a = Leaf | Branch a (Tree a) (Tree a)
  deriving (Functor)

This happens to work in this case, and then you're guaranteed to have a law-abiding instance!

Seriously, this is the way you should typically acquire Functor instances for your data types. But you should still know yourself when it makes sense!

Actual Answer

I want to determine, and not just for this data type, but for others such as String, if these data types are law-abiding instances of Functor

So, for a Functor instance, you first of all need a parametric type, i.e. a “container” that doesn't care what type you store in it. So, strictly speaking the functor shouldn't be a type at all but a type constructor or type-level function^★. Practically speaking, you see that by checking if the data declaration has type variables: in case of Tree you immediately see it in your code

data Tree a = ... ✓

If you don't have the source code handy, you can ask GHCi for the kind:

Prelude> :set -XTypeInType -XNoStarIsType†
Prelude> :k Maybe
Maybe :: Type -> Type  ✓
Prelude> :k String
String :: Type         ✗

As you see, String does not even have a type parameter, so it can't possibly be a functor.^‡

Next, you need to look how the type variable is used in the data structure. If there are multiple type parameters, all of the following applies to the last (rightmost) of them, e.g. in data Either a b = ... we'd be talking about the b parameter.

• If it's not used at all (i.e. if it's a phantom type argument) then you can trivially write a law-abiding Functor instance: just don't use the mapping-function either.

  data Tough a = Tough String
  
  instance Functor Tough where
    fmap _ (Tough s) = Tough s
  

  (However perhaps you shouldn't write a functor instance in this case, because phantom arguments are often meant to be constant unique tags.)

• If it's used directly as part of one of fields in a type constructor, then you can write a functor instance. The fmap-ped function should then be applied to all those values.

  data Maybe a = Nothing
               | Just a
  
  instance Functor Maybe where
    fmap _ Nothing = Nothing
    fmap f (Just a) = Just $ f a
  

• If it's used somewhere deeper nested in the data structure, but all the nesting is in functors itself, then it's a functor. (This also holds up if it's the same functor you're just trying to define yourself, i.e. for recursive types!)

  data TwoLists a = TwoLists {listL :: [a], listR :: [a]}
  
  instance Functor TwoLists where
    fmap f (TwoLists ll lr) = TwoLists (fmap f ll) (fmap f lr)
  

• [Advanced, probably best if you ignore this for now] if the nesting consists of not normal (covariant) functors, but of an even number of contravariant functors, then your whole type is also a covariant functor.

---

^★_{Type constructors are actually a very specific sort of type-level function, in particular they're injective. Mathematically speaking, a functor doesn't need to map its objects injectively (in case of Hask, the objects are types), but in Haskell this is necessary for the type checker.}

^†_{These syntactic extensions cause GHCi to show the kind of types as Type; historically it would show * instead and that's still the default in older GHC version, but now deprecated.}

^‡_{However, String is actually a synonym for [Char] i.e. a list of characters, and list is a functor. So you can actually perform fmap over a string, but that doesn't mean your using the “string functor”: you're using the list functor, and even if you started with a string the result may not be a string (but e.g. a list of integers).}

Answer 2

Try to write such a function. If you succeed, it is definitely a Functor. If you fail, it might not be, or maybe you are not creative enough¹. For Tree, it is relatively straightforward to implement, though of course a beginner may need to ask for help.

Specializing the signature of fmap to your Tree, you want a function with this signature:

mapTree :: (a -> b) -> Tree a -> Tree b
mapTree f Leaf = _
mapTree f (Branch value left right) = _

---

¹ Actually there are many types that you can prove are not Functors just by looking at the fields of their constructors, but since that doesn't apply to Tree we won't get into it.