[Haskell-cafe] Comments from OCaml Hacker Brian Hurt
Bertram Felgenhauer
bertram.felgenhauer at googlemail.com
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
> 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
More information about the Haskell-Cafe
mailing list