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

[Lennart Augustsson]

A very nice writeup about the use of monoid with finger tree.
But please, use the names of the monoid operations that the rest of
the Haskell libraries use.
By using different names you are just confusing readers (even if you
don't like the standard names).

Also, you can replace Infinity by maxBound.

  -- Lennart

On Tue, Jan 20, 2009 at 3:42 PM, Heinrich Apfelmus
<apfelmus at quantentunnel.de> wrote:
> 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
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>