ANN: A Functional Implementation of the Garsia-Wachs Algorithm
Hi All, 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. There was an interesting point to porting it to Haskell, indeed there is a crucial use of first-class references used only locally. A good reason to show the power of the ST monad and it's runST function! Here is the hackage URL: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/garsia-wachs And the darcs 2 URL: http://darcs.feydakins.org/garsia-wachs -- Nicolas Pouillard aka Ertai
nicolas.pouillard:
Hi All,
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.
There was an interesting point to porting it to Haskell, indeed there is a crucial use of first-class references used only locally. A good reason to show the power of the ST monad and it's runST function!
Here is the hackage URL: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/garsia-wachs
And the darcs 2 URL: http://darcs.feydakins.org/garsia-wachs
And packaged for Arch, http://aur.archlinux.org/packages.php?ID=20149 -- Don
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
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
participants (3)
-
Don Stewart -
Nicolas Pouillard -
Ross Paterson