[Haskell-cafe] ANN: A Functional Implementation of the Garsia-Wachs Algorithm

[Nicolas Pouillard]

I've just released an 1.2 version.

Excerpts from Ross Paterson's message of Tue Sep 23 05:03:29 -0700 2008:
> On Mon, Sep 22, 2008 at 11:15:36PM -0700, Nicolas Pouillard wrote:
> > Here is an Haskell implementation of an algorithm that builds a binary
> > tree with minimum weighted path length from weighted leaf nodes given
> > in symmetric order.
> > 
> > This can be used to build optimum search tables, to balance a
> > 'ropes' data structure in an optimal way.
> > 
> > This module a direct translation from OCaml of a functional pearl
> > by Jean-Christophe Filliâtre yesterday on ML Workshop 2008.
> 
> Some minor comments:
> 
> The dependency on containers appears to be unnecessary.

Fixed.

> I wasn't clear what "symmetric order" was.

Yes but I delegate this to the paper.

> It would be useful to have Foldable and Traversable instances for Tree.
> (The latter is mostly there, but inaccessible to clients, and the former
> is easier than treeToList.)

Added.

> Spelling: heights, weights

Also fixed.

Thanks a lot!

-- 
Nicolas Pouillard aka Ertai
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 240 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20080923/c6c78568/signature.bin