-- | 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 -- module Data.Nested.Seq ( module Data.Nested.Seq.Quaternary.Lazy ) where -------------------------------------------------------------------------------- import Data.Nested.Seq.Quaternary.Lazy --------------------------------------------------------------------------------