Monads and the like

What I understand about it now

(Renarks / additions welcome.)

It is all about operations on elements (values or functions), often encapsulated in a structure, a context.
List and Maybe/Option for instance have a compound "kind" (metatype): they need an other type for construction. That makes them the context of the other type.
The operations succeed if those elements or structures obey a number of laws.
Those laws often result in primitives, typeclass-methods.
There are five groups (type-classes) of elements or structures. They obey an increasing number of laws,
- to which lesser and lesser elements abide.
- by which more and more operations are made possible.
There is a cesure between Monoid en Functor (Functor is not a strict subclass of Monoid). Some Monads or Functors can act like a Monoid.
The last remark is not strictly true: Monoids always are concrete types (they don't need a typeparameter, like with Int, or those parameters are filled in, like with List Char).
A Functor (and consequently also a Monad) demands a parameter (is a context).

Laws

In the following S is a set with an associated binary operation O.
Some "synonyms" may concern the same operation, but belong to different levels. Ap in this way is the Monad-version of <*> (Applicative Functor-version).

Closure: Applying O to two elements of S results in an element of S again.
Associativity: When combining pairs of elements order doesn't matter.
(The order of the elements may matter, like in string-concatenation, but not the order of the operations, the location of the parenthesis.
So subtraction is not associatif, (5 - 3) - 4 != 5 - (3 - 4))
Identity or zero: there is an identityelement with an identity operation resulting in the starting-element.
(With addition for instance this is 0, with multiplication 1, when calculating a maximum -∞.)
Compose: f(g(a)) = f•g(a)
Pure, unit or return: def pure[A] (a:A) : F[A]
<*> or ap: def ap[A, B] (fa:F[A]) (fab: F[ A=>B ]) : F[B]
override def map [A,B] (fa: F[A]) (fab: A => B): F[B]=ap(fa)(pure(fab))
flatMap (or bind, >>=)

The benefits of Monads for the programmer

I'm just talking about Monads here. It will be clear that in some cases it is sufficient for instance to be a Functor.

Many standardtypes, like Lists in Haskell and Scala, are bulkcontainers, and often they are Monads too. The same may be the case for self-defined types like a Tree.
Operations on the componenten thereof are often easy to combine or join (composing or chaining).
Other bulkoperations deliver an over-all result (reducing or folding).
"Smaller" standardtypes (like Maybe/Option of Haskell/Scala respectively) can be used to elegantly handle exceptional cases.
If a component doen't exist or results in an exception this can be ignored, or the whole bulkoperation can be cancelled without endless if-then-else, case- or try-catch constructions.
Monads are also used to handle operations with side-effects. This may be about reporting intermediate results (logging), IO-operations, random-input or state-maintenance.
In pure functional code this is all impossible (functions deliver clear-cut results based on their input and don't change anything in the outside world).
Monads however present ways around these problems by incorporating the side-effect in the context and taking care of it in the implementation of >>=.
Especially in Haskell this kind of code is clearly distinguishable from pure functional code. (In Scala it is possible to cheat, but in Haskell side-effects are limited to this kind of Monads.)
In Scala the for-expression or comprehension is the ideal syntax to handle Monads.
Functional languages are characterized by a focus on data-flow in stead of control-flow, and also by the use of very eleborate standardlibraries with optimized standardfunctions
for standard datastructures(that are often Monads).
This in contrast with the OOP (Object Oriented Programming) way of building custom datastructures with custom operations.
The pure functional part of the code is consisting of a bunch of definitions or equations without impact on the outer world (as is usage in math),
more then of a sequence of instructions and statements (changing mutable variables) as is usual in especially imperative, but also OOP-code.
The code is still sequential, but focus is far less on on the order of the instructions, because definitions, once defined, are easely gathered by the compiler.
With lazy evaluation the order even becomes irrelevant.
For this reason it is often said that a functional programmer is more describing the what then the how.

I. Semigroup
Examples Constructor: *	Set of whole numbers with + or * operation: (4 + 10) + 2 = 4 + (10 +2) Examples without identity: positive whole numbers with + operator, or not-empty sequences.
Laws	Closure and Associativity
Operation	append

II. Monoid
Examples	Set of whole numbers with + or * operation: a+0=a, a*1=a Lists, Bool, Ordering, Maybe, selfdefined Tree. Collection with operation, which you (recursively) can expand.
Laws	Like Semigroup, with Identity mempty `mappend` x = x x `mappend` mempty = x (x `mappend` y) `mappend` z = x `mappend` (y `mappend` z) mempty represents the identity-element for a certain monoid with operation, mappend is the binairy function. mconcat is a secundairy function that reduces a list of monoids by a fold-operation to a single value. (mconcat is an unfortunate name, in an addition for instance nothing is joined together.)
Operations	Like Semigroep, with the zero-operation added.

III. Functor
Examples Unary type constructor: -> Binary type constructor: ->->* Functor[F[_]]	Scala: List, Option, Set, Either, Try, Future... Haskell: List, Maybe, eigen Tree, Either, Function ... "Everything that can be mapped over", applying a function to one or more values in a context. Mapping over a function is function-composition (Nicholas, see also LYAH Functor)
Laws	Identity and Compose 1. Indentity fmap id = id 2. Compose fmap (f . g) = fmap f . fmap g , or fmap (f . g) F = fmap f (fmap g F)
Operation	One typeclass-method: fmap :: (a -> b) -> f a -> f b (map is the List-implementation of fmap) Map, Either, Function1 are binary, for which the operation must be applied partially, in steps.

IV. Applicative (-Functor)
Examples	The applied function itself can also be wrapped in a context
Laws	pure f <> x == fmap f x pure id <> v == v pure (.) <> u <> v <> w = u <> (v <> w) pure f <> pure x = pure (f x) u <> pure y = pure ($ y) <> u
Operations	Like Functor, with Pure added (Wraps a value in an applicative), and ap or *<>**(Takes an applicative containing a function and an other applicative, extracts the function(s) from the first and maps it over the second). Applicatives are composable, which is not the case for every Monad.

V. Monad
Examples Higher order type operator: (->)->* Monad[M[_]] M[_] is an unary type-constructor like List or Option	Scala: List, Option, Set, Either, Try, Future... Haskell: List, Maybe, Tree?, Either, ... "Informaly a Monad is everything with a constructor and a flatMap (or bind) method."
Laws	Left identity return x >>= f is the same as f x Right identity m >>= return is the same as m Associativity The result of (m >>= f) >>= g is the same as that of m >>= (\x -> f x >>= g)
Operations `class Applicative m => Monad m where return :: a -> m a (>>=) :: m a -> (a -> m b) -> m b (>>) :: m a -> m b -> m b fail :: String -> m a`	Like Applicative, with bind, >>= or do-notation. (In Scala: flatMap.) Next to bind, return takes care of the wrapping of a value in the monad (a "lift"-function, like pure of the applicative), and >> ("then") takes care of the chaining of monadic actions that don't need the result of the predecessor. fail is just needed internally for pattern-match failures in do-notation.

Just like the Applicative (-Functor), Arrow also is a superclass of Monad, but it doesn't fit well in this scheme. Arrows miss an other law and have a different application-area (i.a. parsers).