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.