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 Fillitre 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.