Home
Reading
Searching
Subscribe
Sponsors
Statistics
Posting
Contact
Spam
Lists
Links
About
Hosting
Filtering
Features Download
Marketing
Archives
FAQ
Blog
 
Gmane
From: Nicolas Pouillard <nicolas.pouillard <at> gmail.com>
Subject: ANN: A Functional Implementation of the Garsia-Wachs Algorithm
Newsgroups: gmane.comp.lang.haskell.cafe
Date: Tuesday 23rd September 2008 06:15:36 UTC (over 8 years 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
 
CD: 3ms