LYAH Chapter 11a - Functors and Functor Laws

Functors redux

• Functors are things that can be mapped over, like lists, Maybes, trees.
• They're described by the typeclass Functor, which has only one typeclass method, namely fmap, which has a type of fmap :: (a -> b) -> f a -> f b. It says: give me a function that takes an a and returns a b and a box with an a (or several of them) inside it and I'll give you a box with a b (or several of them) inside it. It kind of applies the function to the element inside the box.A more correct term for what a functor is would be computational context. The context might be that the computation can have a value or it might have failed (Maybe and Either a) or that there might be more values (lists), stuff like that.
• Functors must take exactly one concrete type as a type parameter: type must be * -> *

Examples of Functors

• IO 
• When we fmap a function over an I/O action, we want to get back an I/O action that does the same thing, but has our function applied over its result value.

1. instance Functor IO where  
2.     fmap f action = do  
3.         result <- action  
4.         return (f result)  

1. import Data.Char  
2. import Data.List  
3.   
4. main = do line <- fmap (intersperse '-' . reverse . map toUpper) getLine  
5.           putStrLn line  

1. $ runhaskell fmapping_io.hs  
2. hello there  
3. E-R-E-H-T- -O-L-L-E-H  

• (->) r
• How are functions functors? Implementation from Control.Monad.Instances :

1. instance Functor ((->) r) where  
2.     fmap f g = (\x -> f (g x))  

• fmap :: (a -> b) -> (r -> a) -> (r -> b) 
•  Another way to write this instance would be:

1. instance Functor ((->) r) where  
2.     fmap = (.)  

• Using fmap over functions is just composition

1. ghci> fmap (*3) (+100) 1  

• Think of the function (+100) as a box that contains its eventual result. Using fmap (*3) on (+100) will create another function that acts like (+100), only before producing a result, (*3) will be applied to that result.
•  Functors allow the result of a computation to be modified with a function.
• Can also think of fmap as a function that takes a function and lifts that function so that it operates on functors.

1. fmap :: (a -> b) -> f a -> f b
2. ghci> :t fmap (*2)  
3. fmap (*2) :: (Num a, Functor f) => f a -> f a  
4. ghci> :t fmap (replicate 3)  
5. fmap (replicate 3) :: (Functor f) => f a -> f [a]  

• The expression fmap (replicate 3) will take a functor over any type and return a functor over a list of elements of that type.

Functor Laws

• Two functor laws that all instances of Functor should abide by - not enforced by Haskell automatically, have to test them out yourself.
•  fmap id  ==  id
• fmap (f . g)  ==  fmap f . fmap g
• Many times, you can intuitively see how these laws hold because the types act like containers or functions. You can also just try them on a bunch of different values of a type and be able to say with some certainty that a type does indeed obey the laws.

Example of Bad Functor that doesn’t follow Laws

• Example of a type constructor being an instance of the Functor typeclass but not really being a functor, because it doesn't satisfy the laws:

1. data CMaybe a = CNothing | CJust Int a deriving (Show)  

1. instance Functor CMaybe where  
2.     fmap f CNothing = CNothing  
3.     fmap f (CJust counter x) = CJust (counter+1) (f x)  

1. ghci> fmap id (CJust 0 "haha")  
2. CJust 1 "haha"  
3. ghci> id (CJust 0 "haha")  
4. CJust 0 "haha"  

CMaybe fails at being a functor even though it pretends to be one, so using it as a functor might lead to some faulty code.
When we use a functor, it shouldn't matter if we first compose a few functions and then map them over the functor or if we just map each function over a functor in succession. But with CMaybe, it matters, because it keeps track of how many times it's been mapped over. Not cool! If we wanted CMaybe to obey the functor laws, we'd have to make it so that the Int field stays the same when we use fmap.

Philosophical Discourse on Functors

• If a type obeys the functor laws, we know that calling fmap on a value of that type will only map the function over it, nothing more. This leads to code that is more abstract and extensible, because we can use laws to reason about behaviors that any functor should have and make functions that operate reliably on any functor.
• We can also look at functors as things that output values in a context. For instance, Just 3 outputs the value 3 in the context that it might or not output any values at all. [1,2,3] outputs three values—1, 2, and 3, the context is that there may be multiple values or no values. The function (+3) will output a value, depending on which parameter it is given.
• If you think of functors as things that output values, you can think of mapping over functors as attaching a transformation to the output of the functor that changes the value.
• When we do fmap (+3) [1,2,3], we attach the transformation (+3) to the output of [1,2,3], so whenever we look at a number that the list outputs, (+3) will be applied to it.
• Another example is mapping over functions. When we do fmap (+3) (*3), we attach the transformation (+3) to the eventual output of (*3).
• Looking at it this way gives us some intuition as to why using fmap on functions is just composition (fmap (+3) (*3) equals (+3) . (*3), which equals \x -> ((x*3)+3)), because we take a function like (*3) then we attach the transformation (+3) to its output. The result is still a function, only when we give it a number, it will be multiplied by three and then it will go through the attached transformation where it will be added to three.

Notes:

• http://book.realworldhaskell.org/read/code-case-study-parsing-a-binary-data-format.html#binary.functor
• We can think of fmap as a kind of lifting function, as we introduced in the section called “Avoiding boilerplate with lifting”. It takes a function over ordinary values a -> b and lifts it to become a function over containers f a -> f b, where f is the container type.
• We can only make instances of Functor from types that have exactly one type parameter.
• We can't write an fmap implementation for Either a b or (a, b), for example, because these have two type parameters. We also can't write one for Bool or Int, as they have no type parameters.