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