[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

[Don Stewart]

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
_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ross Paterson]

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

[Nicolas Pouillard]

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!