-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | A list-like data structure with O(log(n)) random access
--
-- A list-like data structure implemented using a nested data type and
-- polymorphic recursion. It 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 more memory efficient;
-- however, modifying the right end of the sequence is still slow.
@package nested-sequence
@version 0.1
-- | Simple but efficient strict sequence type based on a nested data type
-- and polymorphic recursion.
--
-- 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 and more memory
-- efficient (memory usage is basically the same as with lists: amortized
-- 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 pure random-access stack.
--
-- This module is intended to be imported qualified.
module Data.Nested.Seq.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.Strict.StrictPair a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Nested.Seq.Strict.StrictPair a)
instance GHC.Base.Monoid (Data.Nested.Seq.Strict.Seq a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Nested.Seq.Strict.Seq a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Nested.Seq.Strict.Seq a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Nested.Seq.Strict.Seq a)
instance GHC.Base.Functor Data.Nested.Seq.Strict.Seq
instance Data.Foldable.Foldable Data.Nested.Seq.Strict.Seq
instance GHC.Base.Functor (Data.Nested.Seq.Strict.State t)
instance GHC.Base.Monad (Data.Nested.Seq.Strict.State s)
instance GHC.Base.Applicative (Data.Nested.Seq.Strict.State s)
-- | Simple but efficient lazy sequence type based on a nested data type
-- and polymorphic recursion.
--
-- 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 and more memory
-- efficient (memory usage is basically the same as with lists: amortized
-- 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 pure random-access stack.
--
-- This module is intended to be imported qualified.
module Data.Nested.Seq.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.
--
-- 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.Lazy.Seq a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Nested.Seq.Lazy.Seq a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Nested.Seq.Lazy.Seq a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Nested.Seq.Lazy.Seq a)
instance GHC.Base.Functor Data.Nested.Seq.Lazy.Seq
instance Data.Foldable.Foldable Data.Nested.Seq.Lazy.Seq
instance GHC.Base.Functor (Data.Nested.Seq.Lazy.State t)
instance GHC.Base.Monad (Data.Nested.Seq.Lazy.State s)
instance GHC.Base.Applicative (Data.Nested.Seq.Lazy.State s)
-- | Simple but efficient lazy sequence type based on a nested data type
-- and polymorphic recursion.
module Data.Nested.Seq