Further categories of EM-algebras:

   the distributive law \delta connceting the free monoid monad on
   (-)^* and the (finite) power-set functor can equivalently be
   described in two other forms:

   . a monad on $set$ with the functor (-)^* P and a unit composed of
     the original units (\delta shows up in the multiplication for
     this monad)

   . a monad on $mon$, the category of EM-algebras for the free monoid monad
     that ``lifts'' the (finite) powerset monad.

   fortunately, the categories of EM-algebras for both of these monads
   coincide: 

   . for P we get the category $uqnt$ of unital quantales, i.e.,
     complete lattices with a monoid structure, such that the
     sup-function is a monoid homomorphism; morphisms are
     monoid-homomorphisms that preserve arbitrary suprema.

  . for F we get the category $udioid$ of unital dioids or idempotent
    semi-rings with additive unit.

    recall the notion of 
    - ring, an abelian group <R,+,0> with a monoid structure <R,.,1>
      subject to classical distributivity
    - replacing the abelian group with a commutative monoid yields
      semi-rings with unit, also known as ``rigs'' (ring w/o negatives)
    - replacing the abelian group with a commutative semigroup yields
      semi-rings not neccessarily with unit (``rgs'' anyone?)
    - the commutative monoid/semigroup can also be required to be
      idempotent (a+a=a), which yields dioids or idempotent semirings,
      with or w/o unit

     important examples of idempotent semi-rings in CS are
 
     * the ``tropical'' semiring IR (real numbers) with min as
       addition and + as multiplication; in order to have an additive
       unit, one has to add \infty and gets the ``tropical rig''

     * the ``max-plus-algebra'' IR (real numbers) extended with
       -\infty and with max as addition and + as multiplication.

Sets Bags and Tuples

  . for sets, neither the order of the elements nor the (positive)
    multiplicacy matter

  . for ``bags'', the order does not matter but the multiplicity does
    (sets with possible repetitions)

  . for tuples the order matters, and hence automatically the
    multiplicacy.

  Each of these notions gives rise to a ``finite power-x'' monad:
  . the finite power-set monad on sets, with EM-algebras the
    sup-semilattices (with bottom; in case of non-empty subsets, there
    need not be a bottom element)
  . the finite power-bag monad on set, with EM-algebras the 
    commutative monoids; in case of non-empty bags one gets
    commutative semigroups; idempotent commutative monoids/semigroups
    are just sup-semilattices with or w/o bottom;
  . the ``finite power-tuple'' monad (= free monoid monad) (-)^*, with 
    monoids as EM-algebras; in case of non-empty tuples one gets semigroups.

  The free monoid monad (-)^* admits distributive laws with the other
  two, and the categories of EM-algebras are dioids in case of finite
  power sets, and (unital) semi-rings (rigs) in case of finite power bags.
  
Monads in 2-categories

  The notion of monad makes sense as soon as we have a category whose
  hom-sets are themselves categories (with composition then a family
  of functors).  Besides $cat$ and $Cat$, there are two simpler examples:

  Rel, the category of sets, (bin) relations and inclusions:

  HW: identify the monads in $rel$!

  Spn, the category of sets, spans and span-morphisms: 

    a span from A to B is a set S with maps A <-s_0-- S --s_1-> B; the notion
    is a generalization of directed graphs, in as far as A and B need
    not be the same.  If A <-t_0-- T --t_1-> B is another span from A
    to B, a span-morphism is just a function S --f-> T making both
    triangles commute.

    alternatively, spans from A to B can be viewed as set-valued
    AxB-matrices; their composition is like a matrix product, however
    with disjoint union instead of addition and cartesian product
    instead of multiplication.

  HW: identify the monads in $spn$!

  The other big important notion that can be formulated in any
  2-category is the notion of adjoint.  It may be useful to look at
  adjoints first in simpler cases like $rel$ and $spn$ than in $cat$
  or $Cat$.