Safe Haskell | Safe |
---|---|

Language | Haskell98 |

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