radix-tree

A Haskell library for radix trees.

[!IMPORTANT]

“strict” and “lazy” interfaces within containers and unordered-containers refer to how new values are inserted into the data structures: “strict” means they’re additionally evaluated to WHNF, “lazy” means they aren’t. The data structures themselves are spine-strict in either case.

Within this library “strict” and “lazy” refer to spine-strict and spine-lazy variants of a given data structure respectively. Evaluating the values before inserting them is directly assumed to be user’s responsibility.

Featuring, in order of complexity:

• Data.Patricia.Word.*: a PATRICIA tree.

  The spine-strict variant is effectively identical to containers#IntMap.

• Data.Zebra.Word: a space-partitioning tree based on a PATRICIA tree.

  Similar to a containers#IntSet, a Zebra stores keys more optimally than a naive StrictPatricia (). The approaches are however different:

  • An IntSet stores packs of 32/64 (depending on target platform integer size) adjacent bits together. Fully identical feature-wise to regular IntMaps otherwise.

  • A Zebra partitions the space into black and white zones, effectively storing intervals of colors. This allows for fast range fills (see fillRange) as well as fast lookups of the next key of a particular color (see lookupL and lookupR).

  Due to the way it is constructed a Zebra cannot be spine-lazy.

• Data.RadixTree.Word8.*: a radix tree.

  A general-purpose dictionary type. Asymptotically faster than containers#Map (common key prefixes are only scrutinized once) and far more powerful than unordered-containers#HashMap (no hash collisions, lookups can fail early, tree can be spine-lazy).

  Note that unlike most dictionaries a RadixTree does not have a concrete key type and instead uses two key representations: Feed (a key broken down to individual bytes) and Build (a key reconstructed from chunks as they are found within the tree). It is thus perfectly legal to mix together different key types, as long as they make sense (e.g. a tree of ASCII keys can be treated as a tree of UTF-8 ones at no cost).

• Data.Radix1Tree.Word8.*: a radix tree that cannot store anything at the empty key.

  Exists as a consequence of internal implementation and is convenient for certain formats where empty keys are impossible (such as commandline options and INI files). Fully identical feature-wise to regular RadixTrees otherwise.