| Safe Haskell | Safe |
|---|---|
| Language | Haskell98 |
Data.Nested.Seq
Description
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-listlibrary (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 elementData.Vector: 1 extra word per element