[Haskell-cafe] Re: Comments from OCaml Hacker Brian Hurt

[Heinrich Apfelmus]

david48 wrote:
> On the other hand, on page 320 there is a nice explanation of Monoid,
> and on page 380, which isn't mentionned in the index, there might be
> the first time one can understand why the writer monad works with
> monoids instead of lists: to be able to use better suited data types
> for appending.

(I too usually use the monoid instance mainly for difference lists.)

> All of this is still lacking the great why : why/how an abstraction so
> generic can be useful.
> I'm starting to believe that the only reason to make a datatype an
> instance of Monoid is... why not ! since it's not hard to find an
> associative operation and a neutral element.

As Bertram Felgenhauer has already mentioned, a very powerful
application of monoids are 2-3 finger trees

    Ralf Hinze and Ross Patterson.
    Finger trees: a simple general-purpose data structure.
    http://www.soi.city.ac.uk/~ross/papers/FingerTree.html

Basically, they allow you write to fast implementations for pretty much
every abstract data type mentioned in Okasaki's book "Purely Functional
Data Structures". For example, you can do sequences, priority queues,
search trees and priority search queues. Moreover, any fancy and custom
data structures like interval trees or something for stock trading are
likely to be implementable in this framework as well.

How can one tree be useful for so many different data structures? The
answer: *monoids*! Namely, the finger tree works with elements that are
related to a monoid, and all the different data structures mentioned
above arise by different choices for this monoid.

Let me explain this monoid magic, albeit not in this message which would
become far too long, but at

  http://apfelmus.nfshost.com/monoid-fingertree.html


Regards,
apfelmus

-- 
http://apfelmus.nfshost.com