Functors

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

Two laws:

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

Maybe

Recall mapMaybe from before:

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

Lists

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

Pairs

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

instance Functor_ ((,) a) where
 -- map :: (b -> b') -> (,) a b -> (,) a b'
 -- map :: (b -> b') -> (a, b) -> (a, b')
    map 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 Functor_.map. Like (,), need to partially apply Either to one type. So, must implement "mapRight":

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

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

Note that the following seemingly equivalent definition (notice the Left equation defined in terms of la) does not typecheck because Haskell cannot assign two types (Either a b and Either a b') to the expression la:

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

Functions

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

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. (Recall that we often will use newtype, rather than data, to define datatypes with exactly one one-argument constructor.)

newtype AssocList k v =
  BoxAssocList [(k, v)]

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

instance Functor_ (AssocList k) where
 -- map :: (a -> b) -> (AssocList k) a -> (AssocList k) b
 -- map :: (a -> b) -> AssocList k a -> AssocList k b
 -- map f (BoxAssocList kvs) = BoxAssocList $ Prelude.map (Functor_.map f) kvs
    map f (BoxAssocList kvs) = BoxAssocList $ Functor_.map (Functor_.map f) kvs

If we go back and add record type syntax...

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

... we can simplify the definition a bit further via the automatically generated unboxAssocList accessor function:

instance Functor_ (AssocList k) where
 -- map :: (a -> b) -> AssocList k a -> AssocList k b
 -- map f list = BoxAssocList $ Functor_.map (Functor_.map f) (unboxAssocList list)
 -- map f list = BoxAssocList $ Functor_.map (Functor_.map f) . unboxAssocList $ list
    map f      = BoxAssocList . Functor_.map (Functor_.map f) . unboxAssocList

Aside: 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
 -- map :: (a -> b) -> Compose f g x -> Compose f g x
 -- map f (Compose x) = Compose (Functor_.map (Functor_.map f) x)
    map f             = Compose . Functor_.map (Functor_.map f) . getCompose

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

From Functor_ to Functor

The Functor class defined in Data.Functor (and exposed by Prelude) uses the name fmap rather than map.

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

As mentioned before, there is an infix operator defined to be fmap.

(<$>) = fmap

This allows the expression f <$> x to resemble function application f $ x.

Source Files

• Functor_.hs