nested-sequence-0.2: List-like data structures with O(log(n)) random access
List-like data structures implemented using nested data types and polymorphic
recursion. Also called "n-ary random access lists". They supports O(log(n))
lookup
while still having amortized O(1)
access to the left end of the sequence.
Somewhat similar to finger trees, but much simpler, and the ternary and
quaternary versions are also more memory efficient; however, modifying
the right end of the sequence is still slow. See Data.Nested.Seq
for general comments and Data.Nested.Seq.Binary.Lazy for an explanation
of the data structure.