Understanding category theory for haskeller

This is not another monad tutorial. It is just a note for myself to understand how applicative in Haskell works. And I think you should not need any category knowledge to understand this.

If you want to understand what a monad is, you should understand how functor works, the definition of it. So the dependency will be:

functor → endofunctor → semigroup → monoid → monad → applicative.

Functor

Functor is a characteristic of data that can be mapped over. It means the data can be generalised if you define the operation that map from this to that, and for the data that has this characteristic will able to map data accordingly. Say, lists, array and trees are things that can be mapped over.

The definition of the functor in Haskell is

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

Where the definition of the map function is

        map :: (a -> b) -> [a] -> [b]
        

See the differences? fmap only defines the computation between a to b^[1]. Where map only map a list to a list accordingly to the rules it accepted.

In other words, for any composite (or complicated data structures), if the typeclass Functor instance is defined, it is a functor automatically.

Like Maybe a, the maybe monad

        data Maybe a = Nothing | Just a

        instance Functor Maybe where
            fmap f Nothing = Nothing
            fmap f (Just a) = Just (f a)
        

Functors are required to obey certain laws regards to their mappings.

• Functors must preserve identity morphisms
• Functors preserve composition of morphisms

Endofunctor

Endofunctor is a functor that map a category to itself. The type signature is fairly self-explanatory:

        someEndofunctor :: (a -> b) -> (a -> b)
        

For someEndofunctor, if you apply the function f where f: Int -> String, then the result will be f itself.

So in purely functional paradigm, the list data structure is basically a typical endofunctor, it has methods like head and tail, and the tail return the list itself, without the head value. So you can consume the list recursively.

Semigroup

Semigroup is a characteristic of data that can be appended, and the appended data is a semigroup too.

Monoid

Monoid is semigroup with an identity. An identity means empty, say, any natural number plus zero is equal to the natural number itself, the zero is then an identity in the natural number category. Another example is the empty string ("").

Monad

Monad is a monoid in the category of endofunctors. It allows programmers to compose the computations in a description (eg IO monad, StateT monad...) as it can make computation to carry data and pass to the computation itself, and then execute (lift) at once. **Hmm, basically an action combinator in program**

There is a lot of resources to read

• Understanding monads
• All about monad from Haskell Wiki

Applicative

Applicative are added in Haskell codebase after Monad, but actually it is another special case of functor.

We can have a look from this flip ($) function's type signature:

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

Applicative is technically a functor that has more structure than a functor but less than a monad. ²It is an intermediate class between Functor and Monad.

Applicative are widely used class to compose computations without context. For example:

        -- Maybe is a monad and can pass a generalised a to it
        data Maybe a = Nothing | Just a
        

        Prelude> 2 + 3
        5

        Prelude> (Just 2) + (Just 3)
        error:
            • Non type-variable argument in the constraint: Num (Maybe a)
              (Use FlexibleContexts to permit this)
            • When checking the inferred type
                it :: forall a. (Num a, Num (Maybe a)) => Maybe a
        

As the error stated, we should have a function and a value both wrapped in Maybe monad. So we change our code to this:

        Prelude> ((+) <$> Just 2) <*> Just 3
        Just 5

        Prelude> (Just (+2)) <*> Just 3
        Just 5
        

(<*>) is one of the methods of Applicative, the type class of applicative functors - functors that support function application within their contexts. Expressions such as (+) <$> Just 2 <*> Just 3 are said to be written in applicative style, which is as close as we can get to regular function application while working with a functor. If you pretend for a moment the (<$>), (<*>) and Just aren't there, our example looks just like (+) 2 3

Haskell pattern

Haskellers do like use operators (one word function, aw). Often, Haskell operators are similar and comes with a definite pattern.

• f $ x means f applied to x.
• x & f means f applied to x too. Just like chain operator in F# or future Javascript (|>)
• f <$> x means map f over x.
• x <&> f means map f over x too.

So the <operator> means the map over of the operator itself.