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

[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

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