Subject: ANN: A Functional Implementation of the Garsia-Wachs Algorithm
Newsgroups: gmane.comp.lang.haskell.cafe
Date: 2008-09-23 06:15:36 GMT (40 weeks, 5 days, 16 hours and 13 minutes ago)
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
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe <at> haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe