Chapter 16: Functor

https://hackage.haskell.org/package/base-4.14.1.0/docs/Data-Functor.html https://wiki.haskell.org/Typeclassopedia#Functor

Short summary

What the hell is a functor?

It’s an algebra that lets you map over things! Sometimes this is a data structure, like a list or tree, and sometimes this is computational context, such as Just or Either or IO.

In Haskell there is no way to enforce the laws of a type classes algebra. (Instead we rely on programmer discipline.) So Functor is simply a type class and what it actually does depends on the implementation of the instance declaration for the type in question.

One example of a somewhat counterintuitive Functor instance is the one for pairs, which alters the second element of the tuple, but not the first. Apparently, there is a tradition of treating tuples as name:value pairs, and the instance follows that tradition by not touching the first element.

This is also a consequence of functors kind constraint of (f :: * -> *), which means that any type constructor that can be an instance of Functor must take exactly one argument. This, again, is an implementation detail. Conceptually, n-ary functors exist. To define them in the general case for any number of arguments and type constructors in Haskell would require dependent types, though.

Unlike some other algebras, it can be proven that each type has at most one functor. (Via the free theorem of the type of fmap, whatever the hell that means.)

GHC can even derive Functor for you, if you turn on the DeriveFunctor language pragma.

Examples

>>> fmap (+1) [1..4]
[2,3,4,5]

>>> fmap (+1) (Just 8)
Just 9

>>> fmap show (Just 1)  --  (a   -> b)      -> f a       -> f b
Just "1"                --  (Int -> String) -> Maybe Int -> Maybe String

>>> fmap show Nothing   --  (a   -> b)      -> f a       -> f b
Nothing                 --  (Int -> String) -> Maybe Int -> Maybe String

>>> fmap show [1,2,3]   --  (a   -> b)      -> f a       -> f b
["1", "2", "3"]         --  (Int -> String) -> [Int]     -> [String]

>>> fmap show []        --  (a   -> b)      -> f a       -> f b
[]                      --  (Int -> String) -> [Int]     -> [String]

Laws

• Identity: fmap id \(=\) id

• Composition: fmap (f . g) \(=\) fmap f . fmap g

• Structure preservation

Class methods

• fmap :: (a -> b) -> f a -> f b

• (<$) :: a -> f b -> f a

• {-# MINIMAL fmap #-}

Instances

• (Either a)

• []

• Maybe

• IO

• ((->) r)

• ((,) a)

Where is it defined?

• Prelude

• Data.Functor

• Control.Monad

16.1 Functor

Rudolf Carnap, a logician in the 1930s, coined the term functor to describe grammatical function words that operate over sentences or phrases.

Understanding Functor and Applicative is important to a deep understanding of Monad.

This chapter will include:

• the return of the higher-kinded types;

• fmaps galore, and not only on lists;

• no more digressions about dusty logicians;

• words about type classes and constructor classes;

• puns based on George Clinton music, probably.

16.2 What’s a functor?

A functor is a way to apply a function to the inhabitants of some structure that we don’t want to alter.

-- 16.2 What's a functor, page 628, fig 1
--
--
--              The input
--           type constructor
--         must  take  one type
--         argument  to  become
--           a concrete type.
--            vvvvvvvvvvvvv
class Functor (f :: * -> *) where
  --
  --
  --               This is the
  --               functorial
  --               type   that
  --               contains a.
  --               (By  taking    May be a differnt
  --                it  as  a       type than a.
  --                type arg.)       /
  --                    v           v
  fmap :: (a -> b)  ->  f a  ->  f b
  --      ^^^^^^^^               ^
  --     Function to             |
  --   perform  on  the    This is the same f!
  --    enclosed type.
  --
  --
  -- ⍘(<$)⍘ Has a default definition of ⍘fmap . const⍘.
  (<$) :: a -> f b -> f a
  --
  --
  -- We only need fmap for a complete definition of
  -- this type class (though we should be nice and
  -- follow the Functor laws).
  {-# MINIMAL fmap #-}

16.4 Let’s talk about f baby

We know that the f in our Functor definition must be kind * -> * for a couple of reasons, which we will first describe and then demonstrate:

1. Each argument (and result) in the type signature must be fully applied. Each argument must have the kind *.

2. The type f was applied to a single argument in two different places, f a and f b. Since f a and f b must each have the kind *, f by itself must be kind * -> *.

16.4.1 Shining star come into view

Every argument to the type constructor of -> must be of kind *:

·∾ :kind (->)
(->) :: * -> * -> *

In other words; Each argument and result of every function must be a type constant (or concrete type), rather than a type constructor awaiting arguments.

Given this knowledge, we can know something about Functor from the type of fmap:

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

Remember that type variables are scoped to the type class declaration that introduced them. The f in class Functor (f :: * -> *) where { ... } is the same f within the type signature of everything withing braces.

16.4.5 A shining star for you to see what your f can truly be

Notice a similarity between $ and <$> (infix fmap):

(<$>) :: Functor f => (a -> b) -> f a -> f b
  $   ::              (a -> b) ->   a ->   b

16.17 Chapter Exercises

16.17.1 Valid Functor

Determine if a valid functor can be written for the datatype provided.

1. data Bool = False | True

   Ok, this type doesn’t contain anything, and the entire point of functor is to map over the contents of some structure (or context), so intuitively it doesn’t make sense for functor to work for this type.

   Accordingly, at the implementation level, the kind of Bool is Bool :: *, which doesn’t meet Functor’s kind constraint of (f :: * -> *).

   So we can’t write a lawful instance for this type. But, for all I know, maybe GHC can’t really enforce the kind signature. I know it can’t enforce laws. What will happen if I try?

   This:

   ·∾ :{
    ⋮ instance Functor Bool where
    ⋮   fmap f l = not l
    ⋮ :}
   
   <interactive>:3:18: error:
       • Expected kind ‘* -> *’, but ‘Bool’ has kind ‘*’
       • In the first argument of ‘Functor’, namely ‘Bool’
         In the instance declaration for ‘Functor Bool’
   

   Good. Sane error messages are nice :^).

2. data BoolAndSomethingElse a = False' a | True' a

   Alright! This type constructor takes an argument, and has a structure, so it makes sense to write a functor for it. The fact that the data constructors have the words true and false in them is completely irrelevant – they may as well be named A and B.

   Let me give this a shot:

   ·∾ data BoolAndSomethingElse a = False' a | True' a deriving (Eq, Show)
   
   ·∾ :{
    ⋮ instance Functor BoolAndSomethingElse where
    ⋮   fmap f (False' a) = False' (f a)
    ⋮   fmap f (True' a)  = True' (f a)
    ⋮ :}
   ·∾
   
   ·∾ fmap (*3) (True' 20)
   True' 60
   
   ·∾ fmap (++"?") (False' "what")
   False' "what?"
   

3. data BoolAndMaybeSomethingElse a = Falsish | Truish a

   Alright, this one looks similar to Maybe:

   ·∾ data BoolAndMaybeSomethingElse a = Falsish | Truish a deriving (Eq, Show)
   
   ·∾ :{
    ⋮ instance Functor BoolAndMaybeSomethingElse where
    ⋮   fmap f (Truish a) = Truish (f a)
    ⋮   fmap f Falsish = Falsish
    ⋮ :}
   ·∾
   
   ·∾ fmap (++ "in a bottle") (Truish "a message")
   Truish "a messagein a bottle"
   

4. Use the kinds to guide you on this one, don’t get too hung up on the details.

   newtype Mu f = InF { outF :: f (Mu f) }
   

   This… doesn’t seem right…:

   ·∾ newtype Mu f = InF { outF :: f (Mu f) }
   
   ·∾ :kind Mu
   Mu :: (* -> *) -> *
   
   ·∾ :kind Functor
   Functor :: (* -> *) -> Constraint
   

   I don’t think it’s possible to define an instance for this datatype, but I’ll revisit the problem after I do some more reading in the chapter.

5. Again, follow the kinds and ignore the unfamiliar parts

   import GHC.Arr
   
   data D = D (Array Word Word) Int Int
   

   The kind signature doesn’t match, so I don’t think I can define an instance for it; I’ll revisit this after reading more, though.

   ·∾ import GHC.Arr
   ·∾ data D = D (Array Word Word) Int Int deriving (Eq, Show)
   
   ·∾ :kind D
   D :: *
   
   ·∾ :kind Functor
   Functor :: (* -> *) -> Constraint
   

16.17.2 Constructor shuffle

Rearrange the arguments to the type constructor of the datatype so the Functor instance works.

1. data Sum a b = First a | Second b
   
   instance Functor (Sum e) where
     fmap f (First a)  =  First (f a)
     fmap f (Second b) =  Second b
   

   It compiles!

   
   data Sum b a = First a | Second b
     deriving (Eq, Show)
   
   instance Functor (Sum e) where
     fmap f (First a)  =  First (f a)
     fmap f (Second b) =  Second b
   
   

2. data Company a b c = DeepBlue a c | Something b
   
   instance Functor (Company e e') where
     fmap f (Something b)  =  Something (f b)
     fmap _ (DeepBlue a c) =  DeepBlue a c
   

   I don’t know why this works, but it does.

   
   data Company a c b = DeepBlue a c | Something b
     deriving (Eq, Show)
   
   instance Functor (Company e e') where
     fmap f (Something b)  =  Something (f b)
     fmap _ (DeepBlue a c) =  DeepBlue a c
   
   

3. data More a b = L a b a | R b a b deriving (Eq, Show)
   
   instance Functor (More x) where
     fmap f (L a b a')  =  L (f a) b (f a')
     fmap f (R b a b')  =  R b (f a) b'
   

   Keeping in mind that it should result in a Functor that does the following:

   ·∾ fmap (+1) (L 1 2 3)
   L 2 2 4
   
   ·∾ fmap (+1) (R 1 2 3)
   R 1 3 3
   

   
   data More b a = L a b a | R b a b
     deriving (Eq, Show)
   
   instance Functor (More x) where
     fmap f (L a b a')  =  L (f a) b (f a')
     fmap f (R b a b')  =  R b (f a) b'
   

16.17.3 Write the instance

Write Functor instances for the following datatype.

1. data Quant a b = Finance | Desk a | Bloor b
   

   Alright, here is the first instance:

   
   data Quant a b = Finance | Desk a | Bloor b
     deriving (Eq, Show)
   
   
   instance Functor (Quant a) where
     fmap f Finance   = Finance
     fmap f (Desk a)  = Desk a
     fmap f (Bloor b) = Bloor (f b)
   
   
   -- I don't know what the I'm doing, here. So frustrating!
   instance Arbitrary (Quant Int Int) where
     arbitrary =
       elements ( [ Finance ]
                  ++ take 10 [ (Desk a) | a <- [1..] ]
                  ++ take 10 [ (Bloor a) | a <- [1..] ] )
   
   
   
   --
   

2. No, it’s not interesting by itself.

   data K a b = K a
   

   I still learned something:

   
   --data K a b = K a
   ---- justsomeguy
   ----
   ----   Is it impossible to define an instance of Functor
   ----   for the type ''data K a b = K a''?
   ----
   ----   I keep on getting type errors if I try something
   ----   like ''instance Functor (K a) where { fmap f (K
   ----   a) = K (f a) }''.
   ----
   ---- koz_
   ----
   ----   justsomeguy: That's just Const. So it is very
   ----   possible.
   ----
   ----   The problem you're having is that 'f' has a
   ----   different type to what you're thinking. It's
   ----   not a -> c, it's _b_ -> c.
   ----
   ----   In Const, the second type parameter is phantom.
   ----   So you can change it to whatever whenever.
   ----
   ----   So you just ignore the function and rebuild the
   ----   Const with the same value 'inside' it always had.
   ----
   ----   You can think of 'Const a b' as 'an a pretending
   ----   to be a b'.  So we can have it pretend to be a
   ----   c, and you only pass the function so fmap is happy.
   ----
   ---- So the question becomes, why does f take a "b" as
   ---- input rather than an "a"?
   ----
   ---- It turns out that instance declarations operate on the
   ---- outermost (or rightmost) type argument first. This is
   ---- due to the outermost reduction strategy that Haskell
   ---- employes.
   ----
   ---- More here:
   ----
   ----   https://www.youtube.com/watch?v=QBQ9_9R7o8I
   ----   &list=PLe7Ei6viL6jGp1Rfu0dil1JH1SHk9bgDV
   ----   &index=31
   ----
   ---- One property of the church-rosser theorem is:
   ----
   ---- If there is some reduction strategy that terminates,
   ---- the outermost reduction strategy will *always* terminate.
   ----
   --instance Functor (K a) where
   --  fmap f (K a) = K a
   ---- (K a) b
   ---- fmap
   ---- Prelude> :t K
   ---- K :: a -> K a b
   ---- Prelude> :kind K
   ---- K :: * -> * -> *
   
   
   
   --
   

3. newtype Flip f a b = Flip (f b a) deriving (Eq, Show)
   
   newtype K a b = K a
   
   -- should remind you of an instance you've written before
   instance Functor (Flip K a) where
     fmap = undefined
   

4. data EvilGoateeConst a b = GoatyConst b
   
   -- You thought you'd escaped the goats by now didn't you? Nope.
   

   No, it doesn’t do anything interesting. No magic here or in the previous exercises. If it works, you succeeded.

5. Do you need something extra to make the instance work?

   data LiftItOut f a = LiftItOut (f a)
   

6. data Parrapa f g a = DaWrappa (f a) (g a)

7. Don’t ask for more typeclass instances than you need. You can let GHC tell you what to do.

   data IgnoreOne f g a b =
     IgnoringSomething (f a) (g b)
   

8. data Notorious g o a t =
     Notorious (g o) (g a) (g t)
   

9. You’ll need to use recursion.

   data List a = Nil | Cons a (List a)
   

10. A tree of goats forms a Goat-Lord, fearsome poly-creature.

    data GoatLord a =
        NoGoat
      | OneGoat a
      | MoreGoats (GoatLord a) (GoatLord a) (GoatLord a)
      -- A VERITABLE HYDRA OF GOATS
    

11. You’ll use an extra functor for this one, although your solution might do it monomorphically without using fmap. Keep in mind that you will probably not be able to validate this one in the usual manner. Do your best to make it work.

    data TalkToMe a = Halt | Print String a | Read (String -> a)