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

[Ross Paterson]

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.

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

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.)

Spelling: heights, weights