Thu Jan 15 21:32:46 EST 2009

```Andrew Wagner wrote:
> I think perhaps the correct question here is not "how many instances of
> Monoid are there?", but "how many functions are written that can use an
> arbitrary Monoid". E.g., the fact that there are a lot of instances of Monad
> doesn't make it useful. There are a lot of instances of Monad because it's
> useful to have instances of Monad. Why? Because of
> Look at all the cool stuff you can automagically do with your type just
> because it's an instance of Monad! I think that's the point. What can you do
> with arbitrary Monoids? Not much, as evidenced by

One example where Monoids (in full generality) are useful is that of
measurements in the Data.Sequence paper (which is sadly not implemented
in the library, although it is used to maintain the length for efficient
indexing),

http://www.soi.city.ac.uk/~ross/papers/FingerTree.html

The concept applies to any tree that represents an ordered list.

The basic idea is that given a measurement for single elements,

class Monoid v => Measured a v where
measure :: a -> v

we can annotate a tree with cached measurements of the corresponding
sequences,

data Tree a v = Empty | Leaf v a | Node v (Tree a v) (Tree a v)

measureTree :: Measured a v => Tree a v -> v
measureTree Empty = mzero
measureTree (Leaf v _) = v
measureTree (Node v _ _) = v

which can be calculated easily by smart constructors:

leaf :: Measured a v => a -> Tree a v
leaf a = Leaf (measure a) a

node :: Measured a v => Tree a v -> Tree a v -> Tree a v
node l r = Node (measureTree l `mappend` measureTree r) l r

Because v is a monoid, the construction satisfies the law

measureTree = mconcat . map measure . toList

where
toList Empty = []
toList (Leaf _ a) = [a]
toList (Node _ l r) = toList l ++ toList r

All usually efficient tree operations, insertion, deletion, splitting,
concatenation, and so on, will continue to work, if the cached values
are ignored on pattern matching and the smart constructors are used
for constructing the new trees. measure or `mappend` will be called
for each smart constructor use - if they take constant time, the
complexity of the tree operations doesn't change.

Applications include:
- finding and maintaining the sum of any substring of the sequence.
- maintaining minimum and maximum of the list elements
- maintaining the maximal sum of any substring of the sequence
(this can be done by measuring four values for each subtree:
1. the sum of all elements of the sequence
2. the maximum sum of any prefix of the sequence
3. the maximum sum of any suffix of the sequence
4. the maximum sum of any substring of the sequence)

I also found the idea useful for
http://projecteuler.net/index.php?section=problems&id=220

starting out with
-- L system basis
class Monoid a => Step a where
l :: a
r :: a
f :: a

and then providing a few instances for Step, one of which was a binary
tree with two measurements.

Bertram
```