epicartificials blog

Monads, Monoids and more

Definition from the wiki says:

In functional programming, a monad is a design pattern that allows structuring programs generically while automating away boilerplate code needed by the program logic.

but what does that really mean?

Haskell has types such as Int, String, Bool which are standard types. Then it has custom data-types such as Ord a, Num a, Eq a, Show a that define certain operations for any object of that type. And finally there are things like Monad and Foldable that allow as to define very useful operations on an object. This can greatly improve our code. For much more and detailed information go here.

For now I will look only on a subset of these from the image and those are Functor, Applicative, Monad, Foldable, Traversable, Semigroup and Monoid

Functor

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

    (<$>) = fmap

The Functor class is used to apply a function over a container of values. The container can be anything, for example a list, set, tree, etc.

When defining the functor we need to obey certain rules that ensure that functor behaves like a functor should

fmap id = id
fmap (g . h) = (fmap g) . (fmap h)

The first law says that mapping the identity function over every item in a container has no effect. The second says that mapping a composition of two functions over every item in a container is the same as first mapping one function, and then mapping the other.

Some examples would be

map (+2) [1, 2, 3, 4, 5]    ~>    [3,4,5,6,7]

Applicative

class Functor f => Applicative f where
    pure  :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

The Applicative class is a small modification of Functor. Where Functor gives us fmap which takes a function and applies it to a container, Applicative's <*> (apply) takes an encapsulated function and applies it to a container.

Applicative also has some laws it needs to follow:

pure id <*> v = v                             -- The identity law
pure f <*> pure x = pure (f x)                -- Homomorphism
u <*> pure y = pure ($ y) <*> u               -- Interchange
u <*> (v <*> w) = pure (.) <*> u <*> v <*> w  -- Composition

Some examples would be

[(+2), (+3)] <*> [1, 2, 3, 4, 5]     ~>     [3, 4, 5, 6, 7, 4, 5, 6, 7, 8]

Monad

class Applicative m => Monad m where
    return :: a -> m a
    (>>=)  :: m a -> (a -> m b) -> m b

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

The Monad class is an Applicative that has a lot of similarities. return should behave the same as pure and (>>) should behave the same as (*>). The only difference is the bind operator (>>=) which unpacks and then calls the function with the unpacked value.

Again, Monad has to follow certain rules:

return a >>= k  =  k a
m >>= return    =  m
m >>= (\x -> k x >>= h)  =  (m >>= k) >>= h

Monads allow as to write a short-hand expressions using a do notation. Instead of chaining bind operators we can write the commands under each other in a more imperative style.

Instead of:

--  a >>= \x -> b >> c >>= \y -> d
a >>= \x ->
b >>
c >>= \y ->
d

we can write it as:

do
    x <- a
    b
    y <- c
    d

Semigroup

class Semigroup a where
  (<>) :: a -> a -> a
  sconcat :: NonEmpty a -> a
  stimes :: Integral b => b -> a -> a

Semigroup is defined on a type where the (<>) operator is associative. For example addition on numbers forms a semigroup (a + b) + c = a + (b + c), multiplication on numbers forms a semigroup, minimum and maximum on numbers form a semigroup, etc.

sconcat applies the (<>) operator many times over the container and stimes replicates the container many times concatenated by sconcat.

The only law Semigroup has to follow is

(x <> y) <> z = x <> (y <> z)

which assures associativity.

Monoid

class Monoid a where
    mempty  :: a
    mappend :: a -> a -> a

    mconcat :: [a] -> a

Many semigroups have a neutral element mempty where (x <> e) = (e <> x) = x. For example for addition the neuthral element is 0, for multiplication it is 1.

The laws for Monoid are straight-forward:

mempty `mappend` x = x
x `mappend` mempty = x
(x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)

Foldable

class Foldable t where
    foldr   :: (a -> b -> b) -> b -> t a -> b
    foldMap :: Monoid m => (a -> m) -> t a -> m

    fold    :: Monoid m => t m -> m
    foldr'  :: (a -> b -> b) -> b -> t a -> b
    foldl   :: (b -> a -> b) -> b -> t a -> b
    foldl'  :: (b -> a -> b) -> b -> t a -> b
    foldr1  :: (a -> a -> a) -> t a -> a
    foldl1  :: (a -> a -> a) -> t a -> a
    toList  :: t a -> [a]
    null    :: t a -> Bool
    length  :: t a -> Int
    elem    :: Eq a => a -> t a -> Bool
    maximum :: Ord a => t a -> a
    minimum :: Ord a => t a -> a
    sum     :: Num a => t a -> a
    product :: Num a => t a -> a

The Foldable class represents and object that can be "folded" into one value. Foldable type has to have either foldr or foldMap defined. The rest are just useful functions we can get by combining these two.

Traversable

class (Functor t, Foldable t) => Traversable t where
    traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)
    sequenceA :: Applicative f => t (f a) -> f (t a)
    mapM      ::       Monad m => (a -> m b) -> t a -> m (t b)
    sequence  ::       Monad m => t (m a) -> m (t a)

Traversable class that represents a foldable type where we can traverse the whole container and apply some function to it. traverse is like a map over every element and sequenceA swaps containers inside out.