Accompanying material for

The programs run under Hugs 98 as of September 1999 or February 2001 (or GHC 4.04 or GHC 4.08). Since the code uses rank-2 type signatures Hugs must be called setting the flag -98, for instance, hugs -98 Main.lhs (for GHC add -fglasgow-exts to the command line arguments). NB. Since some of the trie types have second-order kinds, Haskell's Show class cannot be used to print elements of these types. Instead, we have to code the printing routines by hand (employing the technique of polytypic programming once again).

• Introduction.lhs: Code from the introduction.
• Bintree.lhs: External binary search trees.
• Fork.lhs: Internal nodes.
• Perfect.lhs: Perfectly balanced, binary leaf trees.
• Sequ.lhs: Binary random-access lists.
• Encode.lhs: Polytypic data compression (including example calls).
• Map.lhs: Functions shared by all trie structures.
• OrdList.lhs: Finite maps based on ordered association lists.
• MapList.lhs: Spotted tries for lists.
• MapBintree.lhs: Spotted tries for external binary search trees.
• MapFork.lhs: Spotted tries for internal nodes.
• MapPerfect.lhs: Spotted tries for perfect trees.
• MapSequ.lhs: Spotted tries for random-access lists.
• Main.lhs: Example calls.
• Term.lhs: de Bruijn terms.
• MapIncr.lhs: Spotted tries for variables of type Incr v.
• MapTerm.lhs: Spotted tries for de Bruijn terms of type Term v.
• MapTermInt.lhs: Spotted tries for non-closed de Bruijn terms of type Term Int (including example calls).