Functors

class Functor_ (t :: * -> *) where
    fmap :: (a -> b) -> t a -> t b

Notice that we’re explicitly writing KindSignatures just for emphasis.

Two laws:

1. fmap id = id
2. fmap (f . g) = fmap f . fmap g

Maybe

Recall mapMaybe from before:

instance Functor_ Maybe where
 -- fmap :: (a -> b) -> Maybe a -> Maybe b
    fmap f Nothing  = Nothing
    fmap f (Just x) = Just $ f x

Lists

instance Functor_ [] where
 -- fmap :: (a -> b) -> [] a -> [] b
 -- fmap :: (a -> b) -> [a] -> [b]
    fmap = map

Pairs

The pair constructor (,) has kind * -> * -> *. So, to be a Functor_, need to partially apply it to one type.

The type signature for fmap in the class definition refers to bound type variables a and b. So we should think a bit before choosing new variables. One option is to choose some other variable, say x:

instance Functor_ ((,) x) where
 -- fmap :: (a -> b) -> (,) x a -> (,) x b
 -- fmap :: (a -> b) -> (x, a) -> (x, b)

This is fine, but an alternative is to use a as the first argument to the pair type and then rename the a and b in the fmap signature to b and b', respectively. I prefer this setup, because it is common to refer to the component types of a pair with variables a and b, and the similarity between variables b and b' helps to remember their relationship.

instance Functor_ ((,) a) where
 -- fmap :: (b -> b') -> (,) a b -> (,) a b'
 -- fmap :: (b -> b') -> (a, b) -> (a, b')
    fmap f (a, b) = (a, f b)

Either

data Either a b
  = Left a
  | Right b

A very general mapping function would take a function for each variant:

mapEither :: (a -> a') -> (b -> b') -> Either a b -> Either a' b'
mapEither f g (Left a)  = Left $ f a
mapEither f g (Right b) = Right $ g b

But the type of this function doesn’t fit the requirements of fmap. Like (,), need to partially apply Either to one type. So, must implement “mapRight”:

instance Functor_ (Either a) where
 -- fmap :: (b -> b') -> Either a b -> Either a b'
    fmap f (Left a)  = Left a
    fmap f (Right b) = Right $ f b

This is still useful: transform only Right values while simply propagating Left values (often used to represent errors).

Consider the following seemingly equivalent definition — the Left equation usings a variable left_a to match the values Left a:

instance Functor_ (Either a) where
 -- fmap :: (b -> b') -> Either a b -> Either a b'
    fmap f (Right b) = Right $ f b
    fmap f left_a    = left_a

This version does does not typecheck, however, because Haskell assigns only one type to every expression. The variable left_a is assigned type Either a b, but what is needed on the right-hand side is an Either a b'. The value bound to left_a (Left a for some a) can be assigned the desired type, but the variable binding that value has been assigned a different type.

Functions

instance Functor_ ((->) t) where
 -- fmap :: (a -> b) -> ((->) t) a -> ((->) t) b
 -- fmap :: (a -> b) -> (t -> a) -> (t -> b)
 -- fmap :: (a -> b) -> (t -> a) -> t -> b
 -- fmap f g = \t -> f (g t)
 -- fmap f g = f . g
    fmap     = (.)

Box: Wrapper Types (Redux) (Redux)

Here’s a really simple wrapper type. Recall that we often will use newtype, rather than data, to define datatypes with exactly one one-argument constructor…

newtype Box a = Box a

… and that we can use record type syntax to automatically derive accessor, or projection, functions.

newtype Box a =
  Box { unbox :: a }

Even without using record type syntax, we could have, of course, written our own unbox function. Although it is certainly nice to have these projection functions automatically derived, the “real” reason we will often define wrapper types (with record type constructors) in what follows is to work around the rule that, for each type class, there can be at most one instance per type

But while we’re here, let’s observe that Box is a Functor_.

instance Functor_ Box where
 -- fmap :: (a -> b) -> Box a -> Box b
 -- fmap f (Box a) = Box (f a)
 -- fmap f ia      = Box (f (unbox ia))
 -- fmap f ia      = (Box . f . unbox) ia
    fmap f         = Box . f . unbox

Identity

This Box type is defined in the standard library with different names:

newtype Identity a = Identity { runIdentity :: a }

Association Lists

type AssocList k v = [(k, v)]
type AssocList k v = [] (k, v)
type AssocList k v = [] ((,) k v)

What if we want to fmap a function f over an association list of type AssocList k v? The function f must have type (k,v) -> b for some b. That’s fine, but if want to map over just the values in each pair and keep the keys the same, a pattern that seems quite desirable, in practice? What we would like is the composition of the behavior of fmap for lists (i.e. map) and for pairs (in the Functor_ ((,) a) instance above).

Haskell’s language of types provides (curried) type application (including partial application), but there aren’t enough type-level computational features to define a “type-level lambda” equivalent to “\v -> [] ((,) k v)”. So we can’t create an instance definition for AssocList directly (via the [] and (,) and types). Neither can we via the name AssocList, because it is an alias rather than a “real” type. Instances cannot be declaried via aliases to help enforce the one-type, one-instance restriction.

Thus, we must create a wrapper type.

newtype AssocList k v =
  BoxAssocList { unboxAssocList :: [(k, v)] }

AssocList is a Functor_ via a combination of fmap for lists and fmap for pairs:

instance Functor_ (AssocList k) where
 -- fmap :: (a -> b) -> (AssocList k) a -> (AssfocList k) b
 -- fmap :: (a -> b) -> AssocList k a -> AssocList k b
 -- fmap f (BoxAssocList kvs) = BoxAssocList $ map (fmap f) kvs
 -- fmap f box = BoxAssocList $ map (fmap f) (unboxAssocList box)
 -- fmap f box = BoxAssocList $ map (fmap f) . unboxAssocList $ box
    fmap f     = BoxAssocList . map (fmap f) . unboxAssocList

Aside: Type-Level Composition

Thinking back to the “type-level lambda” we wanted to write, it turns out we can factor out that pattern of composition in a more general wrapper type than AssocList above:

newtype Compose f g x =
  Compose { getCompose :: f (g x) }

instance (Functor_ f, Functor_ g) => Functor_ (Compose f g) where
 -- fmap :: (a -> b) -> Compose f g x -> Compose f g x
 -- fmap f (Compose x) = Compose (fmap (fmap f) x)
    fmap f             = Compose . fmap (fmap f) . getCompose

And then:

type AssocList k v =
  Compose [] ((,) k) v

Or:

type AssocList k =
  Compose [] ((,) k)

From Functor_ to Functor

The Functor class is defined in Data.Functor — and exposed by Prelude.

class Functor f where
    fmap :: (a -> b) -> f a -> f b

As alluded to in the “Monad Roadmap”, there is an infix operator defined to be fmap.

(<$>) = fmap

The expression f <$> x resembles, and is equivalent to, the function application fmap f $ x.

Source Files

• Functor_.hs