-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | 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. @package nested-sequence @version 0.2 -- | Strict quaternary random-access lists. -- -- This module is intended to be imported qualified. module Data.Nested.Seq.Quaternary.Strict -- | The strict sequence type. See Data.Nested.Seq.Quaternary.Lazy -- for more information. data Seq a -- | Prepending an element. Worst case O(log(n)), but amortized -- O(1). cons :: a -> Seq a -> Seq a -- | Worst case O(log(n)), amortized O(1) unCons :: Seq a -> Maybe (a, Seq a) -- | Checks whether the sequence is empty. This is O(1). null :: Seq a -> Bool -- | The length of a sequence. O(log(n)). length :: Seq a -> Int -- | The empty sequence. empty :: Seq a -- | Conversion to a list. O(n). toList :: Seq a -> [a] -- | Conversion from a list. O(n). fromList :: [a] -> Seq a singleton :: a -> Seq a pair :: a -> a -> Seq a triple :: a -> a -> a -> Seq a quad :: a -> a -> a -> a -> Seq a -- | First element of the sequence. Worst case O(log(n)), -- amortized O(1). head :: Seq a -> a -- | Tail of the sequence. Worst case O(log(n)), amortized -- O(1). tail :: Seq a -> Seq a -- | Last element of the sequence. O(log(n)). last :: Seq a -> a -- | First element of the sequence. Worst case O(log(n)), -- amortized O(1). mbHead :: Seq a -> Maybe a -- | Tail of the sequence. Worst case O(log(n)), amortized -- O(1). mbTail :: Seq a -> Maybe (Seq a) -- | All tails of the sequence (starting with the sequence itself) tails :: Seq a -> [Seq a] -- | Last element of the sequence. O(log(n)) mbLast :: Seq a -> Maybe a -- | Lookup the k-th element of a sequence. This is worst case -- O(log(n)) and amortized O(log(k)), and quite -- efficient. lookup :: Int -> Seq a -> a mbLookup :: Int -> Seq a -> Maybe a -- | Update the k-th element of a sequence. update :: (a -> a) -> Int -> Seq a -> Seq a -- | Replace the k-th element. replace n x == update (const x) -- n replace :: Int -> a -> Seq a -> Seq a -- | Drop is efficient: drop k is amortized O(log(k)), -- worst case maybe O(log(n)^2) ? drop :: Int -> Seq a -> Seq a -- | O(n) (for large n at least), where n is the -- length of the first sequence. append :: Seq a -> Seq a -> Seq a -- | Take is slow: O(n) take :: Int -> Seq a -> Seq a -- | The sequence without the last element. Warning, this is slow, -- O(n) init :: Seq a -> Seq a -- | The sequence without the last element. Warning, this is slow, -- O(n) mbInit :: Seq a -> Maybe (Seq a) -- | Warning, this is slow: O(n) (with bad constant factor). snoc :: Seq a -> a -> Seq a -- | Stripping the last element from a sequence is a slow operation, -- O(n). If you only need extracting the last element, use -- mbLast instead, which is fast. unSnoc :: Seq a -> Maybe (Seq a, a) -- | Naive implementation of toList toListNaive :: Seq a -> [a] -- | We maintain the invariant that (Z Nil) never appears. This -- function checks whether this is satisfied. Used only for testing. checkInvariant :: Seq a -> Bool -- | Show the internal structure of the sequence. The constructor names -- Z and O come from "zero" and "one", respectively. showInternal :: Show a => Seq a -> String -- | Generates a graphviz DOT file, showing the internal structure -- of a sequence graphviz :: Show a => Seq a -> String instance GHC.Show.Show a => GHC.Show.Show (Data.Nested.Seq.Quaternary.Strict.StrictQuad a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Nested.Seq.Quaternary.Strict.StrictQuad a) instance GHC.Base.Monoid (Data.Nested.Seq.Quaternary.Strict.Seq a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Nested.Seq.Quaternary.Strict.Seq a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Nested.Seq.Quaternary.Strict.Seq a) instance GHC.Show.Show a => GHC.Show.Show (Data.Nested.Seq.Quaternary.Strict.Seq a) instance GHC.Base.Functor Data.Nested.Seq.Quaternary.Strict.Seq instance Data.Foldable.Foldable Data.Nested.Seq.Quaternary.Strict.Seq instance GHC.Base.Functor (Data.Nested.Seq.Quaternary.Strict.State t) instance GHC.Base.Monad (Data.Nested.Seq.Quaternary.Strict.State s) instance GHC.Base.Applicative (Data.Nested.Seq.Quaternary.Strict.State s) -- | Lazy quaternary random-access lists. -- -- This module is intended to be imported qualified. module Data.Nested.Seq.Quaternary.Lazy -- | The lazy sequence type. -- -- The underlying (nested) data structure corresponds to the quaternary -- representation of the length of the list. It looks like this: -- -- 
--   data Seq a
--     = Nil
--     | Zero        (Seq (a,a,a,a))
--     | One       a (Seq (a,a,a,a))
--     | Two     a a (Seq (a,a,a,a))
--     | Three a a a (Seq (a,a,a,a))
--
-- -- Furthermore we maintain the invariant that Zero Nil never -- appears. data Seq a -- | Prepending an element. Worst case O(log(n)), but amortized -- O(1). cons :: a -> Seq a -> Seq a -- | Worst case O(log(n)), amortized O(1) unCons :: Seq a -> Maybe (a, Seq a) -- | Checks whether the sequence is empty. This is O(1). null :: Seq a -> Bool -- | The length of a sequence. O(log(n)). length :: Seq a -> Int -- | The empty sequence. empty :: Seq a -- | Conversion to a list. O(n). toList :: Seq a -> [a] -- | Conversion from a list. O(n). fromList :: [a] -> Seq a singleton :: a -> Seq a pair :: a -> a -> Seq a triple :: a -> a -> a -> Seq a quad :: a -> a -> a -> a -> Seq a -- | First element of the sequence. Worst case O(log(n)), -- amortized O(1). head :: Seq a -> a -- | Tail of the sequence. Worst case O(log(n)), amortized -- O(1). tail :: Seq a -> Seq a -- | Last element of the sequence. O(log(n)). last :: Seq a -> a -- | First element of the sequence. Worst case O(log(n)), -- amortized O(1). mbHead :: Seq a -> Maybe a -- | Tail of the sequence. Worst case O(log(n)), amortized -- O(1). mbTail :: Seq a -> Maybe (Seq a) -- | All tails of the sequence (starting with the sequence itself) tails :: Seq a -> [Seq a] -- | Last element of the sequence. O(log(n)) mbLast :: Seq a -> Maybe a -- | Lookup the k-th element of a sequence. This is worst case -- O(log(n)) and amortized O(log(k)), and quite -- efficient. lookup :: Int -> Seq a -> a mbLookup :: Int -> Seq a -> Maybe a -- | Update the k-th element of a sequence. update :: (a -> a) -> Int -> Seq a -> Seq a -- | Replace the k-th element. replace n x == update (const x) -- n replace :: Int -> a -> Seq a -> Seq a -- | Drop is efficient: drop k is amortized O(log(k)), -- worst case maybe O(log(n)^2) ? drop :: Int -> Seq a -> Seq a -- | O(n) (for large n at least), where n is the -- length of the first sequence. append :: Seq a -> Seq a -> Seq a -- | Take is slow: O(n) take :: Int -> Seq a -> Seq a -- | The sequence without the last element. Warning, this is slow, -- O(n) init :: Seq a -> Seq a -- | The sequence without the last element. Warning, this is slow, -- O(n) mbInit :: Seq a -> Maybe (Seq a) -- | Warning, this is slow: O(n) (with bad constant factor). snoc :: Seq a -> a -> Seq a -- | Stripping the last element from a sequence is a slow operation, -- O(n). If you only need extracting the last element, use -- mbLast instead, which is fast. unSnoc :: Seq a -> Maybe (Seq a, a) -- | Naive implementation of toList toListNaive :: Seq a -> [a] -- | We maintain the invariant that (Z Nil) never appears. This -- function checks whether this is satisfied. Used only for testing. checkInvariant :: Seq a -> Bool -- | Show the internal structure of the sequence. The constructor names -- Z and O come from "zero" and "one", respectively. showInternal :: Show a => Seq a -> String -- | Generates a graphviz DOT file, showing the internal structure -- of a sequence graphviz :: Show a => Seq a -> String instance GHC.Base.Monoid (Data.Nested.Seq.Quaternary.Lazy.Seq a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Nested.Seq.Quaternary.Lazy.Seq a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Nested.Seq.Quaternary.Lazy.Seq a) instance GHC.Show.Show a => GHC.Show.Show (Data.Nested.Seq.Quaternary.Lazy.Seq a) instance GHC.Base.Functor Data.Nested.Seq.Quaternary.Lazy.Seq instance Data.Foldable.Foldable Data.Nested.Seq.Quaternary.Lazy.Seq instance GHC.Base.Functor (Data.Nested.Seq.Quaternary.Lazy.State t) instance GHC.Base.Monad (Data.Nested.Seq.Quaternary.Lazy.State s) instance GHC.Base.Applicative (Data.Nested.Seq.Quaternary.Lazy.State s) module Data.Nested.Seq.Quaternary -- | Strict ternary random-access lists. -- -- This module is intended to be imported qualified. module Data.Nested.Seq.Ternary.Strict -- | The strict sequence type. See Data.Nested.Seq.Ternary.Lazy for -- more information. data Seq a -- | Prepending an element. Worst case O(log(n)), but amortized -- O(1). cons :: a -> Seq a -> Seq a -- | Worst case O(log(n)), amortized O(1) unCons :: Seq a -> Maybe (a, Seq a) -- | Checks whether the sequence is empty. This is O(1). null :: Seq a -> Bool -- | The length of a sequence. O(log(n)). length :: Seq a -> Int -- | The empty sequence. empty :: Seq a -- | Conversion to a list. O(n). toList :: Seq a -> [a] -- | Conversion from a list. O(n). fromList :: [a] -> Seq a singleton :: a -> Seq a pair :: a -> a -> Seq a triple :: a -> a -> a -> Seq a quad :: a -> a -> a -> a -> Seq a -- | First element of the sequence. Worst case O(log(n)), -- amortized O(1). head :: Seq a -> a -- | Tail of the sequence. Worst case O(log(n)), amortized -- O(1). tail :: Seq a -> Seq a -- | Last element of the sequence. O(log(n)). last :: Seq a -> a -- | First element of the sequence. Worst case O(log(n)), -- amortized O(1). mbHead :: Seq a -> Maybe a -- | Tail of the sequence. Worst case O(log(n)), amortized -- O(1). mbTail :: Seq a -> Maybe (Seq a) -- | All tails of the sequence (starting with the sequence itself) tails :: Seq a -> [Seq a] -- | Last element of the sequence. O(log(n)) mbLast :: Seq a -> Maybe a -- | Lookup the k-th element of a sequence. This is worst case -- O(log(n)) and amortized O(log(k)), and quite -- efficient. lookup :: Int -> Seq a -> a mbLookup :: Int -> Seq a -> Maybe a -- | Update the k-th element of a sequence. update :: (a -> a) -> Int -> Seq a -> Seq a -- | Replace the k-th element. replace n x == update (const x) -- n replace :: Int -> a -> Seq a -> Seq a -- | Drop is efficient: drop k is amortized O(log(k)), -- worst case maybe O(log(n)^2) ? drop :: Int -> Seq a -> Seq a -- | O(n) (for large n at least), where n is the -- length of the first sequence. append :: Seq a -> Seq a -> Seq a -- | Take is slow: O(n) take :: Int -> Seq a -> Seq a -- | The sequence without the last element. Warning, this is slow, -- O(n) init :: Seq a -> Seq a -- | The sequence without the last element. Warning, this is slow, -- O(n) mbInit :: Seq a -> Maybe (Seq a) -- | Warning, this is slow: O(n) (with bad constant factor). snoc :: Seq a -> a -> Seq a -- | Stripping the last element from a sequence is a slow operation, -- O(n). If you only need extracting the last element, use -- mbLast instead, which is fast. unSnoc :: Seq a -> Maybe (Seq a, a) -- | Naive implementation of toList toListNaive :: Seq a -> [a] -- | We maintain the invariant that (Z Nil) never appears. This -- function checks whether this is satisfied. Used only for testing. checkInvariant :: Seq a -> Bool -- | Show the internal structure of the sequence. The constructor names -- Z and O come from "zero" and "one", respectively. showInternal :: Show a => Seq a -> String -- | Generates a graphviz DOT file, showing the internal structure -- of a sequence graphviz :: Show a => Seq a -> String instance GHC.Show.Show a => GHC.Show.Show (Data.Nested.Seq.Ternary.Strict.StrictTriple a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Nested.Seq.Ternary.Strict.StrictTriple a) instance GHC.Base.Monoid (Data.Nested.Seq.Ternary.Strict.Seq a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Nested.Seq.Ternary.Strict.Seq a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Nested.Seq.Ternary.Strict.Seq a) instance GHC.Show.Show a => GHC.Show.Show (Data.Nested.Seq.Ternary.Strict.Seq a) instance GHC.Base.Functor Data.Nested.Seq.Ternary.Strict.Seq instance Data.Foldable.Foldable Data.Nested.Seq.Ternary.Strict.Seq instance GHC.Base.Functor (Data.Nested.Seq.Ternary.Strict.State t) instance GHC.Base.Monad (Data.Nested.Seq.Ternary.Strict.State s) instance GHC.Base.Applicative (Data.Nested.Seq.Ternary.Strict.State s) -- | Lazy ternary random-access lists. -- -- This module is intended to be imported qualified. module Data.Nested.Seq.Ternary.Lazy -- | The lazy sequence type. -- -- The underlying (nested) data structure corresponds to the binary -- representation of the length of the list. It looks like this: -- -- 
--   data Seq a
--     = Nil
--     | Zero     (Seq (a,a,a))
--     | One    a (Seq (a,a,a))
--     | Two  a a (Seq (a,a,a))
--
-- -- Furthermore we maintain the invariant that Zero Nil never -- appears. data Seq a -- | Prepending an element. Worst case O(log(n)), but amortized -- O(1). cons :: a -> Seq a -> Seq a -- | Worst case O(log(n)), amortized O(1) unCons :: Seq a -> Maybe (a, Seq a) -- | Checks whether the sequence is empty. This is O(1). null :: Seq a -> Bool -- | The length of a sequence. O(log(n)). length :: Seq a -> Int -- | The empty sequence. empty :: Seq a -- | Conversion to a list. O(n). toList :: Seq a -> [a] -- | Conversion from a list. O(n). fromList :: [a] -> Seq a singleton :: a -> Seq a pair :: a -> a -> Seq a triple :: a -> a -> a -> Seq a quad :: a -> a -> a -> a -> Seq a -- | First element of the sequence. Worst case O(log(n)), -- amortized O(1). head :: Seq a -> a -- | Tail of the sequence. Worst case O(log(n)), amortized -- O(1). tail :: Seq a -> Seq a -- | Last element of the sequence. O(log(n)). last :: Seq a -> a -- | First element of the sequence. Worst case O(log(n)), -- amortized O(1). mbHead :: Seq a -> Maybe a -- | Tail of the sequence. Worst case O(log(n)), amortized -- O(1). mbTail :: Seq a -> Maybe (Seq a) -- | All tails of the sequence (starting with the sequence itself) tails :: Seq a -> [Seq a] -- | Last element of the sequence. O(log(n)) mbLast :: Seq a -> Maybe a -- | Lookup the k-th element of a sequence. This is worst case -- O(log(n)) and amortized O(log(k)), and quite -- efficient. lookup :: Int -> Seq a -> a mbLookup :: Int -> Seq a -> Maybe a -- | Update the k-th element of a sequence. update :: (a -> a) -> Int -> Seq a -> Seq a -- | Replace the k-th element. replace n x == update (const x) -- n replace :: Int -> a -> Seq a -> Seq a -- | Drop is efficient: drop k is amortized O(log(k)), -- worst case maybe O(log(n)^2) ? drop :: Int -> Seq a -> Seq a -- | O(n) (for large n at least), where n is the -- length of the first sequence. append :: Seq a -> Seq a -> Seq a -- | Take is slow: O(n) take :: Int -> Seq a -> Seq a -- | The sequence without the last element. Warning, this is slow, -- O(n) init :: Seq a -> Seq a -- | The sequence without the last element. Warning, this is slow, -- O(n) mbInit :: Seq a -> Maybe (Seq a) -- | Warning, this is slow: O(n) (with bad constant factor). snoc :: Seq a -> a -> Seq a -- | Stripping the last element from a sequence is a slow operation, -- O(n). If you only need extracting the last element, use -- mbLast instead, which is fast. unSnoc :: Seq a -> Maybe (Seq a, a) -- | Naive implementation of toList toListNaive :: Seq a -> [a] -- | We maintain the invariant that (Z Nil) never appears. This -- function checks whether this is satisfied. Used only for testing. checkInvariant :: Seq a -> Bool -- | Show the internal structure of the sequence. The constructor names -- Z and O come from "zero" and "one", respectively. showInternal :: Show a => Seq a -> String -- | Generates a graphviz DOT file, showing the internal structure -- of a sequence graphviz :: Show a => Seq a -> String instance GHC.Base.Monoid (Data.Nested.Seq.Ternary.Lazy.Seq a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Nested.Seq.Ternary.Lazy.Seq a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Nested.Seq.Ternary.Lazy.Seq a) instance GHC.Show.Show a => GHC.Show.Show (Data.Nested.Seq.Ternary.Lazy.Seq a) instance GHC.Base.Functor Data.Nested.Seq.Ternary.Lazy.Seq instance Data.Foldable.Foldable Data.Nested.Seq.Ternary.Lazy.Seq instance GHC.Base.Functor (Data.Nested.Seq.Ternary.Lazy.State t) instance GHC.Base.Monad (Data.Nested.Seq.Ternary.Lazy.State s) instance GHC.Base.Applicative (Data.Nested.Seq.Ternary.Lazy.State s) module Data.Nested.Seq.Ternary -- | Strict binary random-access lists. -- -- This module is intended to be imported qualified. module Data.Nested.Seq.Binary.Strict -- | The strict sequence type. See Data.Nested.Seq.Lazy for more -- detailed information. data Seq a -- | Prepending an element. Worst case O(log(n)), but amortized -- O(1). cons :: a -> Seq a -> Seq a -- | Worst case O(log(n)), amortized O(1) unCons :: Seq a -> Maybe (a, Seq a) -- | Checks whether the sequence is empty. This is O(1). null :: Seq a -> Bool -- | The length of a sequence. O(log(n)). length :: Seq a -> Int -- | The empty sequence. empty :: Seq a -- | Conversion to a list. O(n). toList :: Seq a -> [a] -- | Conversion from a list. O(n). fromList :: [a] -> Seq a singleton :: a -> Seq a pair :: a -> a -> Seq a triple :: a -> a -> a -> Seq a quad :: a -> a -> a -> a -> Seq a -- | First element of the sequence. Worst case O(log(n)), -- amortized O(1). head :: Seq a -> a -- | Tail of the sequence. Worst case O(log(n)), amortized -- O(1). tail :: Seq a -> Seq a -- | Last element of the sequence. O(log(n)). last :: Seq a -> a -- | First element of the sequence. Worst case O(log(n)), -- amortized O(1). mbHead :: Seq a -> Maybe a -- | Tail of the sequence. Worst case O(log(n)), amortized -- O(1). mbTail :: Seq a -> Maybe (Seq a) -- | All tails of the sequence (starting with the sequence itself) tails :: Seq a -> [Seq a] -- | Last element of the sequence. O(log(n)) mbLast :: Seq a -> Maybe a -- | Lookup the k-th element of a sequence. This is worst case -- O(log(n)) and amortized O(log(k)), and quite -- efficient. lookup :: Int -> Seq a -> a mbLookup :: Int -> Seq a -> Maybe a -- | Update the k-th element of a sequence. update :: (a -> a) -> Int -> Seq a -> Seq a -- | Replace the k-th element. replace n x == update (const x) -- n replace :: Int -> a -> Seq a -> Seq a -- | Drop is efficient: drop k is amortized O(log(k)), -- worst case maybe O(log(n)^2) ? drop :: Int -> Seq a -> Seq a -- | O(n) (for large n at least), where n is the -- length of the first sequence. append :: Seq a -> Seq a -> Seq a -- | Take is slow: O(n) take :: Int -> Seq a -> Seq a -- | The sequence without the last element. Warning, this is slow, -- O(n) init :: Seq a -> Seq a -- | The sequence without the last element. Warning, this is slow, -- O(n) mbInit :: Seq a -> Maybe (Seq a) -- | Warning, this is slow: O(n) (with bad constant factor). snoc :: Seq a -> a -> Seq a -- | Stripping the last element from a sequence is a slow operation, -- O(n). If you only need extracting the last element, use -- mbLast instead, which is fast. unSnoc :: Seq a -> Maybe (Seq a, a) -- | Naive implementation of toList toListNaive :: Seq a -> [a] -- | We maintain the invariant that (Z Nil) never appears. This -- function checks whether this is satisfied. Used only for testing. checkInvariant :: Seq a -> Bool -- | Show the internal structure of the sequence. The constructor names -- Z and O come from "zero" and "one", respectively. showInternal :: Show a => Seq a -> String -- | Generates a graphviz DOT file, showing the internal structure -- of a sequence graphviz :: Show a => Seq a -> String instance GHC.Show.Show a => GHC.Show.Show (Data.Nested.Seq.Binary.Strict.StrictPair a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Nested.Seq.Binary.Strict.StrictPair a) instance GHC.Base.Monoid (Data.Nested.Seq.Binary.Strict.Seq a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Nested.Seq.Binary.Strict.Seq a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Nested.Seq.Binary.Strict.Seq a) instance GHC.Show.Show a => GHC.Show.Show (Data.Nested.Seq.Binary.Strict.Seq a) instance GHC.Base.Functor Data.Nested.Seq.Binary.Strict.Seq instance Data.Foldable.Foldable Data.Nested.Seq.Binary.Strict.Seq instance GHC.Base.Functor (Data.Nested.Seq.Binary.Strict.State t) instance GHC.Base.Monad (Data.Nested.Seq.Binary.Strict.State s) instance GHC.Base.Applicative (Data.Nested.Seq.Binary.Strict.State s) -- | Simple but efficient lazy list-like sequence type based on a nested -- data type and polymorphic recursion. Also called "binary random-access -- list" -- -- It is like a list, but instead of O(1) cons/uncons and -- O(k) lookup, we have amortized O(1) cons/uncons and -- O(log(k)) lookup (both are O(log(n)) in the worst -- case). This is somewhat similar to a finger tree (which is also -- represented by a nested data type), but much simpler. Memory usage is -- basically the same as with lists: on average 3 words per element, plus -- the data itself. -- -- However, modifying the right end of the sequence is still slow: -- O(n). This affects the functions snoc, unSnoc, -- append, take, init. Somewhat surprisingly, -- extracting the last element is still fast. -- -- An example usage is a stack. -- -- This module is intended to be imported qualified. module Data.Nested.Seq.Binary.Lazy -- | The lazy sequence type. -- -- The underlying (nested) data structure corresponds to the binary -- representation of the length of the list. It looks like this: -- -- 
--   data Seq a
--     = Nil
--     | Even   (Seq (a,a))
--     | Odd  a (Seq (a,a))
--
-- -- Furthermore we maintain the invariant that Even Nil never -- appears. -- -- If the Odd constructor was missing, this would be a full -- binary tree. Note that the nested data type representation has two -- advantages compared to a naive binary tree type (by which we mean the -- usual data Tree a = Node a a | Leaf a construction): First, -- the type system guarantees the fullness; second, it has smaller memory -- footprint, since in the naive case, the Leaf constructors -- introduce two extra words (a tag word and a pointer). -- -- With the Odd constructor thrown in, this is a sequence of -- larger and larger full binary trees. Looking at the binary -- representation of the length of the list, we will have full binary -- trees corresponding to the positions of 1 digits. -- -- For example, here are how sequences of lengths 4, 5, 6 and 7 are -- represented: -- data Seq a -- | Prepending an element. Worst case O(log(n)), but amortized -- O(1). cons :: a -> Seq a -> Seq a -- | Worst case O(log(n)), amortized O(1) unCons :: Seq a -> Maybe (a, Seq a) -- | Checks whether the sequence is empty. This is O(1). null :: Seq a -> Bool -- | The length of a sequence. O(log(n)). length :: Seq a -> Int -- | The empty sequence. empty :: Seq a -- | Conversion to a list. O(n). toList :: Seq a -> [a] -- | Conversion from a list. O(n). fromList :: [a] -> Seq a singleton :: a -> Seq a pair :: a -> a -> Seq a triple :: a -> a -> a -> Seq a quad :: a -> a -> a -> a -> Seq a -- | First element of the sequence. Worst case O(log(n)), -- amortized O(1). head :: Seq a -> a -- | Tail of the sequence. Worst case O(log(n)), amortized -- O(1). tail :: Seq a -> Seq a -- | Last element of the sequence. O(log(n)). last :: Seq a -> a -- | First element of the sequence. Worst case O(log(n)), -- amortized O(1). mbHead :: Seq a -> Maybe a -- | Tail of the sequence. Worst case O(log(n)), amortized -- O(1). mbTail :: Seq a -> Maybe (Seq a) -- | All tails of the sequence (starting with the sequence itself) tails :: Seq a -> [Seq a] -- | Last element of the sequence. O(log(n)) mbLast :: Seq a -> Maybe a -- | Lookup the k-th element of a sequence. This is worst case -- O(log(n)) and amortized O(log(k)), and quite -- efficient. lookup :: Int -> Seq a -> a mbLookup :: Int -> Seq a -> Maybe a -- | Update the k-th element of a sequence. update :: (a -> a) -> Int -> Seq a -> Seq a -- | Replace the k-th element. replace n x == update (const x) -- n replace :: Int -> a -> Seq a -> Seq a -- | Drop is efficient: drop k is amortized O(log(k)), -- worst case maybe O(log(n)^2) ? drop :: Int -> Seq a -> Seq a -- | O(n) (for large n at least), where n is the -- length of the first sequence. append :: Seq a -> Seq a -> Seq a -- | Take is slow: O(n) take :: Int -> Seq a -> Seq a -- | The sequence without the last element. Warning, this is slow, -- O(n) init :: Seq a -> Seq a -- | The sequence without the last element. Warning, this is slow, -- O(n) mbInit :: Seq a -> Maybe (Seq a) -- | Warning, this is slow: O(n) (with bad constant factor). snoc :: Seq a -> a -> Seq a -- | Stripping the last element from a sequence is a slow operation, -- O(n). If you only need extracting the last element, use -- mbLast instead, which is fast. unSnoc :: Seq a -> Maybe (Seq a, a) -- | Naive implementation of toList toListNaive :: Seq a -> [a] -- | We maintain the invariant that (Z Nil) never appears. This -- function checks whether this is satisfied. Used only for testing. checkInvariant :: Seq a -> Bool -- | Show the internal structure of the sequence. The constructor names -- Z and O come from "zero" and "one", respectively. showInternal :: Show a => Seq a -> String -- | Generates a graphviz DOT file, showing the internal structure -- of a sequence graphviz :: Show a => Seq a -> String instance GHC.Base.Monoid (Data.Nested.Seq.Binary.Lazy.Seq a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Nested.Seq.Binary.Lazy.Seq a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Nested.Seq.Binary.Lazy.Seq a) instance GHC.Show.Show a => GHC.Show.Show (Data.Nested.Seq.Binary.Lazy.Seq a) instance GHC.Base.Functor Data.Nested.Seq.Binary.Lazy.Seq instance Data.Foldable.Foldable Data.Nested.Seq.Binary.Lazy.Seq instance GHC.Base.Functor (Data.Nested.Seq.Binary.Lazy.State t) instance GHC.Base.Monad (Data.Nested.Seq.Binary.Lazy.State s) instance GHC.Base.Applicative (Data.Nested.Seq.Binary.Lazy.State s) module Data.Nested.Seq.Binary -- | 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: -- -- module Data.Nested.Seq