garsia-wachs-1.1: A Functional Implementation of the Garsia-Wachs Algorithm

Data.Algorithm.GarsiaWachs

Description

This module a direct translation from ML of the functional pearl A Functional Implementation of the Garsia-Wachs Algorithm

This pearl was presented by Jean-Christophe Fillitre on the ML Workshop 2008.

Quote from the paper:

```  This functional pearl proposes an ML implementation of the
Garsia-Wachs algorithm. This somewhat obscure algorithm builds
a binary tree with minimum weighted path length from weighted
leaf nodes given in symmetric order. Our solution exhibits the usual
benefits of functional programming (use of immutable data structures,
pattern-matching, polymorphism) and nicely compares to
the purely imperative implementation from The Art of Computer
Programming.
```
```  The Garsia-Wachs algorithm addresses the following problem.
Given a sequence of values X0, ..., Xn, together with nonnegative
integer weights w0, ..., wn, we want to construct a binary tree with
X0, ..., Xn as leaf nodes in symmetric order, such that the sum
```
```         sum [ w!i * d!i | i <- [i..n] ]
```
```  is minimum, where di is the distance of leaf node Xi to the root.
```
```  This can be used to build optimum search tables, when data is
organized within a binary search tree and when access frequencies
are known in advance. It may also be used to balance a `ropes`
data structure in an optimal way, since a rope is precisely a
binary tree with a character string on each leaf; thus taking
wi as the length of this string would minimize the average
access cost to a character in the rope.
```

# Documentation

data Tree a Source

Constructors

 Leaf a Node !(Tree a) !(Tree a)

Instances

 Functor Tree Eq a => Eq (Tree a) Show a => Show (Tree a)

garsiaWachs :: (Ord i, Num i) => [(a, i)] -> Maybe (Tree a)Source