main.lhs

> {-# LANGUAGE ExplicitForAll, RankNTypes #-}

> import Control.Monad.Cont

An Eilenberg-Moore algebra for a monad t (a t-algebra) is one of these:

> type Algebra t x = t x -> x

satisfying these laws (page 3):

a . return = id
a . fmap a = a . join

Here's a simple example:

> h :: Algebra [] Int
> h = sum

For t=[], a t-algebra is a rule for reducing a list to a single element. The
laws say that this reduction can be performed by breaking the list up into
pieces which can be reduced in parallel and recombined. (Actually, a []-algebra
is just a monoid.)

The folklore theorem on page 7 is given by this pair of isomorphisms:

> iso :: (Monad t, Functor t) => Algebra t c -> (forall a . t a -> Cont c a)
> iso a u = cont $ \g -> a (fmap g u)

> iso' :: (forall a . t a -> Cont c a) -> Algebra t c
> iso' sigma = \u -> runCont (sigma u) id

For the case t=[] the isomorphism says that reduction rules satisfying the
Eilenberg-Moore rules are the same as a map-reduce operation satisfying certain
rules.

> mapReduce h f l = runCont (iso h l) f

> example = mapReduce h (^2) [1..10]

I'll leave monads other than [] as an exercise.