Haskell: Explanation of Functors & Natural Transformations

functor_examples.md

Functor Examples

Const

(not to be confused with the function const)

newtype Const a b = Const { getConst :: a }

instance Functor (Const a) where
  fmap _ (Const a) = Const a

Const functor holds no elements. Sorry that's not precisely true. Const by itself is not a functor. Const a is the functor. Const is simply a type constructor. When you try to map (fmap f) this functor, the mapping function is simply dropped, and the returned result is the same thing as before. It becomes a "constant" functor, a functor that doesn't change.

import Control.Applicative (Const(Const))

let object1 = Const "hello" -- Const String b

let object2 = fmap (&& False) object1 -- Functor f => f Bool

let object3 = fmap (\_ -> 1.2 :: Double) object2 -- Functor f => f Double

getConst object3 -- "hello"

We can see that Functor f => f b is the same as Const String b. The type inference at the point of mapping the functor forgets about Const String and just considers it to be a functor f b. The b in the end doesn't matter. It is just inferred to whatever the last mapping function returns, but in the end it doesn't do anything. In the end we can still get the "hello" string out of the object. Thus it's a functor that doesn't hold anything, and is useful we need to hide some value that can be carried in the computational context while the context is being mapped.

There is also Data.Functor.Constant, it operates in the same way.

Identity

(not to be confused with the function id)

newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
    fmap f (Identity x) = Identity (f x)

Identity functor holds only 1 element. When you try mapping this functor, it just applies to the function to the value and returns. It's a trivial functor that has no significance in its computational context.

import Data.Functor.Identity

let object1 = Identity "meh" -- Functor f => f [Char]

let object2 = fmap (const "yawn") object1

let Identity x = object2

x -- "yawn"
runIdentity object2 -- "yawn"

It can be used to wrap a variable in a trivial functor so that it can be mapped by a lifted operator. It can also serve as the base monad (monads are functors) to which a series of monad transformed may be applied to construct a composite monad.

Function

data (->) a b

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

Functions are also functors. The function data type declaration has no value constructors. This is because function declaration is special, and is done with a equal sign or lambda syntax. Any function that accepts one parameter is a functor. Mapping the functor is equivalent to composition. The function's body acts like the computational context.

let object1 = (+) 1

let object2 = fmap object1 (*2) -- Num a => a -> a

let object3 = fmap object2 (*3)

let object4 = fmap object3 (/2) -- Fractional a => a -> a

object4 5 -- 16.0

let object1 = (+) 1

let object2 = fmap (*2) object1

let object3 = fmap (*3) object2

let object4 = fmap (/2) object3 -- Fractional a => a -> a

object4 5 -- 18.0 

One major difference is that because we can fmap a function to a function, we can choose the order of composition. The 1st iteration goes backwards (/2, *3, *2, +1), the 2nd iteration goes forwards (+1, *2, *3, /2). This is because functions are contravariant functors a.k.a. "cofunctors". Most functors are covariant functors like the functors defined above.

Furthermore the extraction of the value inside the functor's computational context is done by applying the resulting function to one more value. In essence the value that we are fmapping is the computational itself. Everytime we map the functor, we are sequentially changing the computation. In order to know what the computation does at the end, we have to put a value in. Applying the value is the equivalent expression to using runIdentity or getConst.

functors&natural_transformations.md

                In the Category of Haskell Types (Hask)

                             f: X -> Y                          
                                                                
    +----------------------------------------------------------+
    |                                                          |
    |                    + +                                   |
    |               [[]] | |                                   |
    |                    v | [[X]] -> [[Y]]                    |
    |      [[]]            |                         [[]]      |
    |    +------> [[X]] +------------------> [[Y]] <------+    |
    |    |                 |                              |    |
    |    |          +      |                   +          |    |
    |    +          |      |                   |          +    |
    |               |      |                   |               |
    +--+ X       nx |      | []                | ny       Y <--+
                    |      |                   |                
         +          |      |                   |          +     
         |          v      v                   v          |     
         |                                                |     
         +-------> [X]  +------------------>  [Y] <-------+     
            []                                        []        
                             [X] -> [Y]                         

Natural transformations are morphisms between functors.

Functors are morphisms between categories.

In the category of Hask (of Haskell types), all functors are endofunctors (functors to the same category). These are functors from Hask -> Hask.

There is no requirement of a functor to be a set total function.

In our simplified model of Hask, we have:

• 2 basic primitive types: X and Y.
• 1 basic morphism f: X -> Y.
• 2 functors: [] and [[]]

The [] and [[]] functor maps a primitive type in the category of Hask to composite type in the category of Hask.

• [] maps a to [] a => [] a = [a].
• [[]] maps a to [[]] a => [[]] a = [[a]].

Functors also maps morphisms.

• [] maps f: X -> Y to [] f: [] X -> [] Y => [f]: [X] -> [Y].
• [[]] maps f: X -> Y to [[]] f: [[]] X -> [[]] Y => [[f]]: [[X]] -> [[Y]].

If you look at functors in the category of categories, a functor looks like a single morphism arrow between 2 categories. However within a particular category (such as Hask), an (endo)functor is actually a collection of morphisms from primitive objects to composite objects and primitive morphism arrows to composite morphism arrows. Thus a functor is the very definition of a polymorphic function, it is not one morphism, it is many morphisms!

In the above diagram and explanations we have implied that [] or [[]] is not only the functor, but the specific value level operations that you would use in Haskell to map type objects (X) and type morphisms (X -> Y). This is not true. For example the list constructor [] in Haskell cannot map a morphism. If I create a function func :: X -> Y, and I try passing this func to [], I do not get a new function [X] -> [Y]. All I get is [func]. Instead I need to use an fmap.

The fmap :: Functor F => (a -> b) -> F a -> F b polymorphic function, when applied to a morphism fmap f, will return Functor F => F X -> F Y. The F generalises any kind of functor, and the specific functor is only realised upon application of a particular composite variable.

This reveals to us, that the definition of a functor is actually composed of 2 sub-morphisms:

• constructor - maps objects to objects ([] or [[]])
• fmap - maps morphisms to morphisms

This is implemented through a typeclass and datatype declarations. The typeclass gives us a polymorphic fmap, while the typeclass instance type associates the constructor [] and [[]]. Without these 2 properties/laws, a type constructor cannot be called a functor.

This is of course slightly confusing. But we now realise the meaning of these are:

data [] a = [] | a : [a]

instance Functor [] where
    fmap = map

-- this is what map is:
-- map _ []     = []
-- map f (x:xs) = f x : map f xs

1. data [] a is a type universe function. A.K.A. the functor!
2. [] | a : [a] is the value universe constructor component "object to object" morphism of the [] a functor.
3. fmap is the value universe component "function to function" morphism of [] a functor.

Therefore in our diagram, our use of [] and [[]] is just using the type universe functor. Such a functor works regardless of whether its parameter is a object or morphism. However at the value universe, we need to use either the constructor or the fmap.

Furthermore our functors in this case are not just endofunctors, but are covariant functors. A special case of contravariant functors is when mapping morphisms, they reverse the resulting output. So instead of F f: [X] -> [Y] we get F f: [Y] -> [X]. Most functors we care about will be covariant functors.

We have polymorphic morphism mapping, why not polymorphic object mapping? Well the polymorphic morphism mapping is convenience. We could just as easily have unique morphism mapping functions for each functor. Something like fmap[] and fmap[[]]. We can't really have polymorphic object mapping, because we need to start somewhere, and the compiler can't just guess what kind of composite object you're trying to create. How does it know you want [a] or [[a]]? Only once we know exactly the [a] or [[a]] can we even use the polymorphic morphism mapping function.

This now makes natural transformations easy. A natural transformation maps one functor to another functor. Hence a natural transformation on [[]] -> [] can transform [[X]] -> [X] or [[Y]] -> [Y]. If a functor is considered a collection of morphisms then a natural transformation is also a collection of morphisms. What kind of function looks like [[]] -> []? It's concat! Mapping a functor to the same functor is just a lifted primitive morphism. If we are mapping from one functor to another functor, then we're using a natural transformation. Natural transformations just repackages the functor, it never affects the values inside the functor.

One important lesson here, is that my confusion regarding calling lists a functor, is because this definition is very overloaded. We need to decompose the semantics of such a statement. We have list types, an inhabited variable that has the type of a list of x, where x can be anything. We have the list constructor, the list typeclass instance and the list functor. We have lots of things we group under the definition of a list. So that's why it's not very precise to call list a functor. Specifically the only thing of a list that is actually a functor, is the function [] a in the type universe that resembles an endofunctor in the category of Hask. Everything else is either constructions or dependencies of this concept.

A functor is sufficiently general that it doesn't just apply to container-like type constructors, but any kind of computational context. What's really cool about Haskell, is that every type constructor (with at least 1 parameter) that you create can end up being either a covariant functor or a contravariant functor. This is the power of algebraic data types. In fact there is an extension called DeriveFunctor that can automatically derive Functor instances and fmap implementations for most (any?) covariant functors.