nested-sequence-0.2: List-like data structures with O(log(n)) random access

Safe HaskellSafe



Simple but efficient lazy list-like sequence types based on nested data types and polymorphic recursion. These support amortized O(1) access to the left end of the list, but O(log(n)) lookup and update. Think of these as "better lists". Also called "random-access lists".

Some general comments about the library:

This library implements several variants of the same idea (binary, ternary, and quaternary; lazy and strict). If you want to study it, look at the lazy binary one: Data.Nested.Seq.Binary.Lazy; that's the simplest, and there are some explanation with pictures. If you want to use it, use the lazy quaternary one: that's the fastest and most memory efficient. This module re-exports the latter.

A note about running times: For some operations, like cons, we promise better amortized running time than worst case. Since we are talking about immutable data structures here, by "amortized" we mean something weaker than the usual definition in a mutable setting; namely, what we promise that if in a program the distribution of the sizes of the sequences can be considered uniformly random (on some large interval), then the average running time of those operations are strictly better than the worst case. For example, building a large list by repeated cons-ing is O(n), not O(n*log(n)), since the sizes of the intermediate lists are distributed uniformly.

Comparison of the average memory footprint of some similar data structures:

  • naive binary tree (data on the leaves only): 5 extra words per element
  • binary tree with data on both the leaves and nodes: 3 extra words per element
  • list: 3 extra words per element
  • Data.Nested.Seq.Binary: 3 extra words per element
  • the random-access-list library (from Hackage): 3 extra words per element
  • Data.Sequence (from containers): 2.5 extra words per element
  • Data.Nested.Seq.Ternary: 2 extra words per element
  • Data.Nested.Seq.Quaternary: 1.6666 extra words per element
  • n-ary version of this data structure: (n+1)/(n-1) extra words per element
  • Data.Vector: 1 extra word per element