[Haskell-cafe] Comments from OCaml Hacker Brian Hurt

[Bertram Felgenhauer]

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
> http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad.html !
> 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
> http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Monoid.html

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