Author: Eiko

Tags: Haskell, Haskell Magic, category theory, functor, monad, applicative, binding operator, natural transform, Kleisli category

Time: 2024-09-10 16:42:07 - 2024-09-10 16:42:07 (UTC)

Introduction to Haskell Magic - Lecture 4 Basic Arrow Magic (Category Theory), Functors and Monads

Warning: Advanced Mathematics Ahead

These contents are not taught in other tutorials, but they can greatly increase your understanding of functors and monads! They also contain many of my personally devised insights.

Arrow Magic (Basic Category Theory)

Review the concept of sets. In the category of sets, we not only discuss sets $X,Y,\dots$, but also the relationships between sets, namely functions $$f:X\to Y$$

Sets can be seen as a collection of objects gathered together. However, sets themselves do not remember the relationships between these objects. Categories, on the other hand, can be seen as an “upgraded” version of sets (strictly speaking, the objects in a category do not need to form a set, this is a small category).

We say that a category $\mathcal{C}$ is defined by the following information:

1. It contains a class of objects $\mathrm{ob}(\mathcal{C})$, which is a set. Usually, we simply denote an element $A\in \mathrm{ob}\mathcal{C}$ as $A\in \mathcal{C}$.

2. For every two objects $A,B\in \mathcal{C}$, there is a set $\mathrm{Hom}(A,B)$, whose elements are all the arrows $f:A\to B$, called morphisms, from $A$ to $B$. Moreover, there is a canonical element $1_A:A\to A$ in $\mathrm{Hom}(A,A)$, called the identity element or unit element.

3. For every three objects $A,B,C\in \mathcal{C}$, there exists a composition mapping $$\circ :\mathrm{Hom}(B,C)\times \mathrm{Hom}(A,B)\to \mathrm{Hom}(A,C)$$ $$(g,f)\mapsto g\circ f$$

4. This composition satisfies the associative law, and $1_A$ is the identity element under this composition. $$(f\circ g)\circ h=f\circ (g\circ h),$$ $$1_A\circ f=f,g\circ 1_A=g.$$

Category is an upgraded version of set

Example:

1. The universal set and all set-theoretic functions between sets form a category $\mathbf{Sets}$, called the category of sets. Objects: $$\{1,2\},\varnothing ,\mathbb{R},\mathbb{Z},\{0,5,6\},\dots$$ Morphisms (arrows): $$\{1,2\}\to \{\text{True},\text{False}\},\varnothing \to A,\dots$$

2. The universal $k$-vector space and all linear functions between them form a category ${\mathbf{Vect}}_k$. $$0,V,W,\dots$$ $$V\to W,\dots$$

3. In Haskell, all basic types, user-defined types, and the types formed by combining them, together with the functions that can be defined between these types, form a category $\mathbf{Hask}$. The objects in this category are: $$\mathbf{Int},\mathbf{Double},[\mathbf{Integer}],\mathbf{String},\mathrm{MyDataType}\mathbf{Int},(),\dots$$ The morphisms (arrows) in this category are: $$(+1):\mathbf{Int}\to \mathbf{Int},\mathrm{print}:\mathbf{String}\to \mathbf{IO}(),\dots$$ For simplicity and to make it easier for everyone to understand, we will refer to this category as $\mathbf{Types}$.

Functors are mappings between categories

You can think of categories as an upgraded version of sets, where they not only remember a class of objects, but also remember the relationships between these objects and their compositions.

Since the sets $C$ and $D$ have been upgraded to categories $\mathcal{C}$ and $\mathcal{D}$, the mapping between sets $f:C\to D$ should also be upgraded to a “functor” $F:\mathcal{C}\to \mathcal{D}$.

A mapping between sets only needs to correspond any object $c\in C$ in $C$ to an object $f(c)\in D$ in $D$. This is because there is no relationship between these objects, so you can correspond them arbitrarily. $$C\stackrel{f}{\to }D$$ $$c\mapsto f(c)$$

However, objects in a category are connected by arrows, so a functor not only needs to correspond objects $C\in \mathcal{C}$ in $\mathcal{C}$ to objects $F(C)\in \mathcal{D}$ in $\mathcal{D}$, but also needs to correspond arrows $f:A\to B$ in $\mathcal{C}$ to arrows $F(f):F(A)\to F(B)$ in $\mathcal{D}$. $$\mathcal{C}\stackrel{F}{\to }\mathcal{D}$$

$$A\to F(A)$$

$$(A\stackrel{f}{\to }B)\to (F(A)\stackrel{F(f)}{\to }F(B))$$

And this correspondence process cannot break the composition rule of categories $$F(g\circ f)=F(g)\circ F(f).$$ Note that the left side $g\circ f$ is the composition in category $\mathcal{C}$, while the right side $F(g)\circ F(f)$ is the composition in category $\mathcal{D}$.

If $F$ satisfies the above requirements, $F$ is called a functor from $\mathcal{C}$ to $\mathcal{D}$, or a covariant functor.

If $F$ satisfies the above requirements, but the composition law is reversed $$F(g\circ f)=F(f)\circ F(g),$$ then $F$ is called a contravariant functor.

You can think of a functor as an upgraded version of a mapping, which not only maps elements to elements, but also maps relationships to relationships.

Examples of Functors

1. We can forget the structure of a vector space and reduce it to a set. This correspondence is a functor from ${\mathbf{Vect}}_k$ to $\mathbf{Sets}$, known as the forgetful functor. This functor preserves the composition law, as the mappings and compositions of vector spaces must first be mappings and compositions on sets.

2. The process of mapping any type $a$ in $\mathbf{Types}$ to $[a]$ is a functor from $\mathbf{Types}$ to $\mathbf{Types}$. First, we can construct $[a]$ for any type $a$, and for any function $f:a\to b$ between types, we can construct $\mathrm{map}f:[a]\to [b]$, which preserves function composition: $$\mathrm{map}(f\circ g)=\mathrm{map}f\circ \mathrm{map}g$$

3. Similarly, the process of mapping a type $a$ to a type $\mathbf{Maybe}a$ is a functor $\mathbf{Types}\to \mathbf{Types}$. For any type $a$, we can construct $\mathbf{Maybe}a$, and when there is a mapping $f:a\to b$, we can construct a mapping $\mathrm{maybeMap}f:\mathbf{Maybe}a\to \mathbf{Maybe}b$

maybeMap :: (a -> b) -> Maybe a -> Maybe b
maybeMap f Nothing  = Nothing
maybeMap f (Just a) = Just (f a)

It obviously satisfies the law of composition

maybeMap (f . g) = maybeMap f . maybeMap g
-- both sides are Nothing if input is Nothing.
-- both sides are Just (f (g a)) if input is Just a

1. Hom functor. $\mathrm{Hom}(A,)$ is a functor from category $\mathcal{C}$ to the category of sets $\mathbf{Sets}$. It maps an object $B$ to the set $\mathrm{Hom}(A,B)$, and a morphism $B\stackrel{\alpha }{\to }C$ to a mapping of sets $$\mathrm{Hom}(A,B)\to \mathrm{Hom}(A,C)$$ $$(A\stackrel{f}{\to }B)\mapsto \alpha \circ f=(A\stackrel{f}{\to }B\stackrel{\alpha }{\to }C)$$ It obviously satisfies the law of composition, when there is $B\stackrel{\alpha }{\to }C\stackrel{\beta }{\to }D$: $$(\beta \circ \alpha )\circ f=\beta \circ (\alpha \circ f).$$

2. Hom functor in Haskell. The previous example appears exactly the same in Haskell, except that we are considering the functor from $\mathbf{Types}$ to itself, (a ->) :: Type -> Type, which is in line with the spirit of $\mathrm{Hom}(A,)$ . The action of this functor on mappings is composition.

homMap :: (a -> b) -> (c -> a) -> (c -> b) -- here the functor is (c ->)
homMap = (.) -- if you use eta reduction
-- homMap f g = f . g

Functor class

In fact, in Haskell, these Type Constructors are all functors: IO, Maybe, [], Data.Map, (a ->)… The following Functor class is defined in the Haskell standard library: (These functors are all covariant functors)

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

    (<$>) = fmap -- the functor operator, they are identical functions.

This allows you to use these different functors with just fmap.

safeSqrt :: Double -> Maybe Double
(*10) :: Double -> Double -- well, in fact (Num a) => a -> a
fmap (*10) :: Maybe Double -> Maybe Double -- well, in fact, (Functor f, Num a) => f a -> f a
fmap (*10) . safeSqrt :: Double -> Maybe Double

checkValidPassword :: String -> Maybe String

getLine :: IO String

```Haskell
-- in the number guessing game, we used some functor magic
readMaybe input :: Maybe Integer
compare :: (Ord a) => a -> a -> Ordering
compare secretNumber :: Integer -> Ordering
fmap (compare secretNumber) :: Maybe Integer -> Maybe Ordering

In the number guessing game, we used some functor magic. readMaybe input :: Maybe Integer is the same as compare :: (Ord a) => a -> a -> Ordering. compare secretNumber :: Integer -> Ordering is the same as fmap (compare secretNumber) :: Maybe Integer -> Maybe Ordering.

The set of all functors from category $\mathcal{C}$ to category $\mathcal{D}$, denoted $\mathrm{Fun}(\mathcal{C},\mathcal{D})$, is itself a category. The objects are functors, and the morphisms are called natural transformations. Specifically, given two functors $$F,G:\mathcal{C}\to \mathcal{D}$$ a natural transformation $\eta :F\Rightarrow G$ is a family of morphisms in $\mathcal{D}$ $${\eta }_C:F(C)\to G(C)$$ that are compatible with the functorial morphisms: for any morphism $f:A\to B$ in $\mathcal{C}$, we have $F(f):F(A)\to F(B)$ and $G(f):G(A)\to G(B)$, and the following two compositions are equal as elements of ${\mathrm{Hom}}_{\mathcal{D}}(F(A),G(B))$: $$F(A)\stackrel{{\eta }_A}{\to }G(A)\stackrel{G(f)}{\to }G(B)$$ $$F(A)\stackrel{F(f)}{\to }F(B)\stackrel{{\eta }_B}{\to }G(B)$$

Natural Transformations in Haskell

In Haskell, a natural transformation between functors f and g should be a family of mappings from f a to g a, defined for all a (unrestricted polymorphic function).

natural :: FunctorF a -> FunctorG a

-- examples abound:
repeat :: a -> [a]  
-- this is a natural transform from 1_Types (identity functor) to [] (list functor).

tail :: [a] -> [a]
-- A natural transformation from the list functor [] to itself.

const :: a -> (b -> a)
-- A natural transformation from 1_Types to (b ->)

Monad is a special functor $T:\mathcal{C}\to \mathcal{C}$ from a category to itself. We first note that functors from $\mathcal{C}$ to itself can be composed, just like mappings can be composed. If a ‘multiplication’ for the functor $T$ is defined, the composition of $T$ with itself can be combined into a single composition: $$\mu :T\circ T\Rightarrow T$$ and this ‘multiplication’ satisfies the associative law: $$T^3=T\circ (T\circ T)\stackrel{1_T\mu }{\Rightarrow }T\circ T\stackrel{\mu }{\Rightarrow }T$$ $$T^3=(T\circ T)\circ T\stackrel{\mu 1_T}{\Rightarrow }T\circ T\stackrel{\mu }{\Rightarrow }T$$ The associative law requires that these two are equal as elements of $\mathrm{Fun}(T^3,T)$, and this multiplication has a unit element $\eta$: $$\eta :1_{\mathcal{C}}\Rightarrow T$$ Here, $1_{\mathcal{C}}:\mathcal{C}\to \mathcal{C}$ is the identity functor that does nothing, and satisfies the unit law for multiplication: $$T=1_{\mathcal{C}}\circ T\stackrel{\mu }{\Rightarrow }T$$ $$T=T\circ 1_{\mathcal{C}}\stackrel{\mu }{\Rightarrow }T$$ The unit law requires that both of these are equal to the identity natural transformation $1_T:T\Rightarrow T$ in $\mathrm{Nat}(T,T)$, which does nothing.

Therefore, we say that $T$ is a Monad. In other words, a Monad $T$ is an endofunctor on $\mathcal{C}$ that comes with two natural transformations: $$\mu :T^2\Rightarrow T,\eta :1\Rightarrow T$$ and satisfies the associative and unit laws. If you know what a Monoidal category is, this means that a Monad is a Monoidal object in the Monoidal category $\mathrm{End}(\mathcal{C})$.

Equivalent Definition of Monad Using Binding Operator

In Haskell, the definition of Monad requires two polymorphic functions on type a without restrictions (thus, they are natural transformations of functors on the category Types).

join :: (Monad m) => m (m a) -> m a -- mu, the multiplication of the monad.

return :: (Monad m) => a -> m a  -- eta, unit of the monad

However, in Haskell, the definition of Monad is not the multiplication (join) mentioned above, but a binding operator (>>=).

(>>=) :: (Monad m) => m a -> (a -> m b) -> m b

It can be proven that giving join and giving (>>=) are equivalent, we can use the functor property to turn $a\to Tb$ into $Ta\to T^{2}b$, then apply it to $Ta$, and finally use multiplication $T^{2}b\to Tb$ to get $Tb$.

ma >>= f  = join $ fmap f ma
-- or...
(>>=) = flip $ (join .) . fmap -- I spend 5 minutes trying to write this
-- equivalently,
(>>=) = fmap join . flip fmap
-- Challenge : can you understand these two expressions?
-- Hint:
-- fmap :: (a -> m b) -> m a -> m m b
-- join :: m m b -> m b
-- ((join .) .) :: (d -> c -> m m b) -> (d -> c -> m b)
-- (join .) . fmap :: (a -> m b) -> m a -> m b
-- flip is a standard function that swaps the two arguments of a two-variable function

In turn, if we are given (>>=), we can obtain multiplication $T^{2}a\to Ta$, simply by replacing the type variable a in (>>=) with m a and b with a.

m (m a) -> (m a -> m a) -> m a

The mapping m a -> m a in the middle can be taken as the identity mapping.

The Kleisli category is defined as the function join which is equivalent to the function >>= id in Haskell.

When a Monad $T$ is given on a category $\mathcal{C}$, we can consider a new category $K(\mathcal{C},T)$, where the objects are the same as those in $\mathcal{C}$, but the morphisms are all arrows of the form $a\to Tb$ (called Kleisli arrows). This category $K(\mathcal{C},T)$ is called the Kleisli Category.

Composition of arrows is given by the following method: if we have $a\to Tb$ and $b\to Tc$, we can first use the functor property of $T$ to obtain an arrow $Tb\to T^{2}c$, and then use the ‘multiplication’ natural transformation ${\mu }_c:T^{2}c\to Tc$ from the Monad property of $T$ to connect these two arrows, resulting in

$$a\to Tb\stackrel{T(b\to Tc)}{\to }{T}^{2}c\stackrel{{\mu }_c}{\to }Tc$$

This is an arrow of $a\to Tc$.

In other words, we have a function $$\mathrm{Hom}(a,Tb)\times \mathrm{Hom}(b,Tc)\to \mathrm{Hom}(a,Tc)$$ In Haskell, it can be represented as this operator:

(<=<) :: (Monad m) => (b -> m c) -> (a -> m b) -> a -> m c
-- the composition of Kleisli Arrows
-- Challenge : can you write the definition of (<=<) using join, in a pointless way?

-- we also have an opposite arrow
(>=>) :: (Monad m) => (a -> m b) -> (b -> m c) -> a -> m c

Monads in Haskell

IO Monad

newtype IO a = IO a -- you are not allowed to use this constructor, though

- IO a represents an action on the external world,
- when completed, will return a value of type a

instance Functor IO where
    fmap fab (IO a) = -- wait for IO a to return a value a, and then apply fab

This multiplication obviously satisfies the associative law, and its unit element is

$${\eta }_a:a\to \mathbf{IO}a$$

It wraps a value of type $a$ into an action that does nothing and directly returns $a$.

After defining this multiplication and unit, we can obtain that IO is a Monad.

Maybe Monad

Similarly, we notice that two possibly failing actions can be combined into one possibly failing action $${\mu }_a:\mathbf{Maybe}(\mathbf{Maybe}a)\to \mathbf{Maybe}a$$

You can think of Maybe a as a “Schrödinger’s box”, which may contain an object of type a (Just a), or it may contain nothing (Nothing). When we have two of these boxes, one nested inside the other, we can combine them into one equivalent box. When either layer is Nothing, we consider the box to give us Nothing, and when both layers give us Just (Just a), we consider the box to give us Just a. This way, we combine the two layers of Maybe into one.

join :: Maybe (Maybe a) -> Maybe a
join (Nothing)       = Nothing
join (Just Nothing)  = Nothing
join (Just (Just a)) = Just a

maybe >>= klei 
    = join $ fmap klei maybe
    = case maybe of
        Just a  -> klei a
        Nothing -> Nothing

The unit of multiplication is a mapping that does nothing but put a determined value into a box:

$${\eta }_a:a\to \mathbf{Maybe}ax\mapsto \mathrm{Just}x$$

return :: a -> Maybe a
return x = Just x

List Monad

Two layers of $[[a]]$ can be combined into one layer $[a]$ through concat, which gives a multiplication that satisfies the associative law $${\mu }_a:[[a]]\to [a].$$

join :: [[a]] -> [a]
join = concat

list >>= klei 
    = join $ fmap klei list
    = concat (map klei list)

Its unit is a function that wraps a value into a single-element list $${\eta }_a:a\to [a]$$

return :: a -> [a]
return x = [x]

State Monad

The State Monad is a type of monad that allows for stateful computations. It is commonly used in functional programming languages to manage and manipulate state within a program.

Either Monad

The Either Monad is a type of monad that represents computations that can result in either a successful value or an error. It is often used to handle error handling and branching in functional programming.

do-notation

The do-notation is a syntax for writing imperative-style code in a functional programming language. It allows for a more readable and intuitive way of working with monads, such as the State Monad and Either Monad.

The multiplication and unit of Monad allow us to express many sequential calculations and compositions. Thanks to the associativity, we can also use the concise and vivid do-notation to manage the composition of Monad.

main :: IO ()
main = getLine >>= (\input -> putStrLn input) -- or just getLine >>= putStrLn

-- equivalent way in do-notation
main = do 
    input <- getLine -- do notation is a syntax sugar, it is equivalent to the above
    putStrLn input

main = do
    putStrLn "name?"
    name <- getLine
    putStrLn "age?"
    age <- getLine
    putStrLn $ "Your name and age is" ++ show (name, age)

-- This code is equivalent to:
main = putStrLn "name?" >>= 
         (\_ -> getLine >>= 
           (\name -> putStrLn "age?" >>= 
             (\_ -> getLine >>= 
               (\age -> putStrLn ("Your name and age is " ++ show (name, age)) 
               )
             )
           )
         )

The code above prompts the user for their name and age, and then prints out a message with their name and age. The do notation is used to make the code more readable and easier to understand. However, it can be rewritten using the >>= operator, which is used to chain together multiple actions. Each action is executed sequentially, with the result of the previous action being passed as an argument to the next action. This allows for a more concise and functional style of programming.

Monad is a typeclass in Haskell that represents computations that can be sequenced and composed. It is defined by the following functions:

1. return :: a -> m a - takes a value and wraps it in the monad type constructor.
2. >>= :: m a -> (a -> m b) -> m b - takes a monad value and a function that takes a normal value and returns a monad value, and applies the function to the value inside the monad.
3. >> :: m a -> m b -> m b - takes two monad values and returns the second one, discarding the first one.
4. fail :: String -> m a - takes a string and returns a monad value that represents a failure.

The return function is used to lift a value into a monad, while the >>= function is used to sequence computations. The >> function is similar to >>=, but it discards the result of the first computation. The fail function is used for error handling in monads.

Monads must also follow three laws: left identity, right identity, and associativity. These laws ensure that monads behave predictably and can be composed in a consistent manner.

We have clearly described the mathematical definition of Monad, which is equivalent to giving join and return in Haskell, and is also equivalent to giving (>>=) and return. However, if you want to define a Monad m in Haskell, Haskell requires you to first implement the Functor class for m (as expected) and the Applicative class (a new concept!).

Applicative Functor

class Functor f => Applicative f where
    pure  :: a -> f a  -- this is just the unit, or 'return'
    (<*>) :: f (a -> b) -> f a -> f b -- this allows you to apply a function value as a functor

Let’s first explain why a Monad naturally becomes an Applicative functor.

The <*> function takes two monadic values, mf and ma, and applies the function f from mf to the value a from ma, resulting in a new monadic value mb. This can be written using the do notation as follows:

(<*>) :: m (a -> b) -> m a -> m b
mf <*> ma = do
    f <- mf
    a <- ma
    return $ f a

Alternatively, it can be written using the >>= operator and lambda expressions:

mf <*> ma = mf >>= (\f -> ma >>= (\a -> return (f a)))

Therefore, Monads are all Applicatives, but not all Applicatives are Monads. Therefore, Applicative is a weaker concept than Monad in Haskell.

Example: Defining Maybe as a Monad

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

The Maybe type is an instance of the Applicative and Monad typeclasses. The pure function takes a value and wraps it in a Just constructor. The <*> operator takes a Maybe value containing a function and a Maybe value containing a value, and applies the function to the value, returning a new Maybe value. If either of the Maybe values is Nothing, the result is also Nothing.

The return function is the same as the pure function. The >>= operator takes a Maybe value and a function that takes a value and returns a Maybe value. If the Maybe value is Just, the function is applied to the value and the result is returned. If the Maybe value is Nothing, the result is also Nothing.

• Now you can use do-notation to chain a sequence of Maybe maps！

myCalculation :: String -> Maybe Double
myCalculation input = do
    x <- readMaybe input
    y <- safeSqrt x
    z <- safeSqrt (1 - y)
    return z

Summary

1. Category is an upgraded version of a set, which not only remembers the elements, but also remembers the arrows between these elements and the composition of arrows.

2. Functor is an upgraded mapping, which not only corresponds to elements, but also corresponds to arrows and maintains the composition of arrows. In Haskell, the functor mapping is unified by fmap or <$>.

3. Monad is a special endofunctor, which comes with two natural transformations, multiplication $\mu$ and unit $\eta$. It needs to satisfy the associativity and unit laws. In Haskell, it is written as join and return, and Haskell uses an equivalent but different definition, using the binding operator (>>=) instead of multiplication join.

4. IO, Maybe, [], Data.Map, (a ->) are all examples of functors in Haskell.

5. IO, Maybe, [] are all examples of monads in Haskell.

6. In Haskell, monads naturally become applicative functors, and in Haskell you need to define applicative before defining monad.