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.

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

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)

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