Simple examples to illustrate Category, Monoid and Monad?

Question

I am getting very confused with these three concepts.

Is there any simple examples to illustrate the differences between Category, Monoid and Monad ?

It would be very helpful if there is a illustration of these abstract concepts.

Stakhanovism

Have you read the Typeclassopedia? – Teakettle

Thanks for your advice. I should have read it first. – Stakhanovism

Monads are like burritos. Really. – Ifill

Answer 1

This probably isn't the answer you're looking for, but here you go anyways:

A really crooked way of looking at monads & co.

One way of looking at abstract concepts like these is to link them with basic concepts, such as ordinary list processing operations. Then, you could say that,

• A category generalizes the (.) operation.
• A monoid generalizes the (++) operation.
• A functor generalises the map operation.
• An applicative functor generalizes the zip (or zipWith) operation.
• A monad generalizes the concat operation.

A Category

A category consists of a set (or a class) of objects and bunch of arrows that each connect two of the objects. In addition, for each object, there should be an identity arrow connecting this object to itself. Further, if there is one arrow (f) that ends on an object, and another (g) that starts from the same object, there should then also be a composite arrow called g . f.

In Haskell this is modelled as a typeclass that represents the category of Haskell types as objects.

 class Category cat where
  id :: cat a a
  (.) :: cat b c -> cat a b -> cat a c

Basic examples of a category are functions. Each function connects two types, for all types, there is the function id :: a -> a that connects the type (and the value) to itself. The composition of functions is the ordinary function composition.

In short, categories in Haskell base are things that behave like functions, i.e. you can put one after another with a generalized version of (.).

A Monoid

A monoid is a set with an unit element and an associative operation. This is modelled in Haskell as:

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

Common examples of monoids include:

• set of integers, the element 0, and the operation (+).
• set of positive integers, the element 1, and the operation (*).
• set of all lists, the empty list [], and the operation (++).

These are modelled in Haskell as

newtype Sum a = Sum {getSum :: a}
instance (Num a) => Monoid (Sum a) where
  mempty  = Sum 0
  mappend (Sum a) (Sum b) = Sum (a + b)  

instance Monoid [a] where
  mempty = []
  mappend = (++)

Monoids are used to 'combine' and accumulate things. For example, the function mconcat :: Monoid a => [a] -> a, can be used to reduce a list of sums to single sum, or a nested list into a flat list. Consider this as a kind of generalization of (++) or (+) operations that in a way 'merge' two things.

A Functor

A functor in Haskell is a thing that quite directly generalizes the operation map :: (a->b) -> [a] -> [b]. Instead of mapping over a list, it maps over some structure, such as a list, binary tree, or even an IO operation. Functors are modelled like this:

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

Contrast this to the definition of the normal map function.

An Applicative Functor

Applicative functors can be seen as things with a generalized zipWith operation. Functors map over general structures one at the time, but with an Applicative functor you can zip together two or more structures. For the simplest example, you can use applicatives to zip together two integers inside the Maybe type:

pure (+) <*> Just 1 <*> Just 2  -- gives Just 3

Notice that the structure can affect the result, for example:

pure (+) <*> Nothing <*> Just 2  -- gives Nothing

Contrast this to the usual zipWith function:

zipWith (+) [1] [2]  

Instead of of just lists, the applicative works for all kinds of structures. Additionally, the clever trickery with pure and (<*>) generalizes the zipping to work with any number of arguments. To see how this works, inspect the following types while keeping the concept of partially applied functions at hand:

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

Notice also the similarity between fmap and (<*>).

A Monad

Monads are often used to model different computational contexts, such as non-deterministic, or side-effectful computations. Since there are already far too many monad tutorials, I will just recommend The best one, instead of writing yet another.

Relating to the ordinary list processing functions, monads generalize the function concat :: [[a]] -> [a] to work with many other sorts of structures besides lists. As a simple example, the monadic operation join can be used to flatten nested Maybe values:

join (Just (Just 42)) -- gives Just 42
join (Just (Nothing)) -- gives Nothing

How is this related to the use of Monads as a means of structuring computations? Consider a toy example where you do two consecutive queries from some database. The first query returns you some key value, with which you wish to do another lookup. The problem here is that the first value is wrapped inside Maybe, so you can't query with that directly. Instead, as maybe is a Functor, you could instead fmap the return value with the new query. This would give you two nested Maybe values like above. Another query would result in three layers of Maybes. This would be quite difficult to program with, but a monadic join gives you a way to flatten this structure, and work with just a single level of Maybes.

(I think I'll be editing this post a lot before it makes any sense..)

Lovettalovich

mempty = 0 should be mempty = Sum 0. – Wriggly

I like this answer, but you might want to point out that the standard Applicative instance for [] is not the zippy one, but the cartesian product. The not-very-useful zippy list monad is only valid on lists of consistent length and its join is taking the diagonal. – Idiocy

@C.A.McCann Applicative Functors are "zippy" in another sense, aren't they, in a sense of having a method fzip :: (f a, f b) -> f (a,b), combining two fs into one. (cf. https://mcmap.net/q/245167/-more-fun-with-applicative-functors). – Ifill

@WillNess: Typically, the phrase "zippy Applicative" means an instance that behaves as a structural intersection, matching elements from two structures that have the same position. Such an fzip implemented with Applicative may not behave like zip with other instances, the obvious example being the default list instance, where fzip would give the full cartesian product. – Idiocy

@C.A.McCann yes, apparently I skipped the word "also" there, as in "are also ''zippy'' in another sense ...". – Ifill

Answer 2

I think to understanding monads one needs to play with bind operator (>>=). Heavilty influenced by [http://dev.stephendiehl.com/hask/#eightfold-path-to-monad-satori](Don't read the monad tutorials.)

My little play is the following:

1. Concat getLine and putStrLn

Adapted from http://www.haskellforall.com/2014/10/how-to-desugar-haskell-code.html

Prelude> f = getLine >>= \a -> putStrLn a
Prelude> f
abc
abc
Prelude>

and the signatures:

Prelude> :t getLine
getLine :: IO String
Prelude> :t (\a -> putStrLn a)
(\a -> putStrLn a) :: String -> IO ()
Prelude> :t f
f :: IO ()

Result: one can see parts of (>>=) :: Monad m => m a -> (a -> m b) -> m b signature.

2 . concat Maybe's

Adaptation from https://wiki.haskell.org/Simple_monad_examples

Prelude> g x = if (x == 0) then Nothing else Just (x + 1)
Prelude> Just 0 >>= g
Nothing
Prelude> Just 1 >>= g
Just 2

Result: fail "zero" is Nothing

3. Think of bind as joining the computations

... as described in https://www.slideshare.net/ScottWlaschin/functional-design-patterns-devternity2018

Lithography