| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Unison.Util.Deque
Description
A strict finger tree: see Unison.Util.Deque.Internal, which has the implementation and also exports the parts that Unison.Util.Rope shares.
Synopsis
- data Deque a
- type Seq = Deque
- pattern Empty :: Deque a
- pattern (:<|) :: a -> Deque a -> Deque a
- pattern (:|>) :: Deque a -> a -> Deque a
- empty :: Deque a
- singleton :: a -> Deque a
- cons :: a -> Deque a -> Deque a
- snoc :: Deque a -> a -> Deque a
- append :: Deque a -> Deque a -> Deque a
- (<|) :: a -> Deque a -> Deque a
- (|>) :: Deque a -> a -> Deque a
- (><) :: Deque a -> Deque a -> Deque a
- fromList :: [a] -> Deque a
- fromListN :: Int -> [a] -> Deque a
- unsafeFromListN :: Int -> [a] -> Deque a
- fromFunction :: Int -> (Int -> a) -> Deque a
- size :: Deque a -> Int
- length :: Deque a -> Int
- null :: Deque a -> Bool
- lookup :: Int -> Deque a -> Maybe a
- toList :: Deque a -> [a]
- uncons :: Deque a -> Maybe (a, Deque a)
- unsnoc :: Deque a -> Maybe (Deque a, a)
- take :: Int -> Deque a -> Deque a
- drop :: Int -> Deque a -> Deque a
- splitAt :: Int -> Deque a -> (Deque a, Deque a)
- sort :: Ord a => Deque a -> Deque a
- sortBy :: (a -> a -> Ordering) -> Deque a -> Deque a
- unstableSort :: Ord a => Deque a -> Deque a
- unstableSortBy :: (a -> a -> Ordering) -> Deque a -> Deque a
- intersperse :: a -> Deque a -> Deque a
- reverse :: Deque a -> Deque a
- valid :: Deque a -> Either String ()
The type
Instances
| Eq1 Deque Source # | |
| Ord1 Deque Source # | |
Defined in Unison.Util.Deque.Internal | |
| Show1 Deque Source # | |
| Functor Deque Source # | |
| Foldable Deque Source # | |
Defined in Unison.Util.Deque.Internal Methods fold :: Monoid m => Deque m -> m # foldMap :: Monoid m => (a -> m) -> Deque a -> m # foldMap' :: Monoid m => (a -> m) -> Deque a -> m # foldr :: (a -> b -> b) -> b -> Deque a -> b # foldr' :: (a -> b -> b) -> b -> Deque a -> b # foldl :: (b -> a -> b) -> b -> Deque a -> b # foldl' :: (b -> a -> b) -> b -> Deque a -> b # foldr1 :: (a -> a -> a) -> Deque a -> a # foldl1 :: (a -> a -> a) -> Deque a -> a # elem :: Eq a => a -> Deque a -> Bool # maximum :: Ord a => Deque a -> a # minimum :: Ord a => Deque a -> a # | |
| Traversable Deque Source # | Rebuilds the sequence. O(n). |
| NFData a => NFData (Deque a) Source # | The structure is always evaluated; this evaluates the elements fully. |
Defined in Unison.Util.Deque.Internal | |
| Monoid (Deque a) Source # | |
| Semigroup (Deque a) Source # | |
| IsList (Deque a) Source # | |
| Show a => Show (Deque a) Source # | |
| Eq a => Eq (Deque a) Source # | |
| Ord a => Ord (Deque a) Source # | Lexicographic, as for lists. |
Defined in Unison.Util.Deque.Internal | |
| type Item (Deque a) Source # | |
Defined in Unison.Util.Deque.Internal | |
Construction
fromList :: [a] -> Deque a Source #
O(n). A fold, so that it fuses with a list that is being produced.
fromListN :: Int -> [a] -> Deque a Source #
fromList for a list whose length is known. O(n). Exactly n
elements are taken; a shorter list is an error. (unsafeFromListN is
the same without the check, for a caller that built the list to length.)
unsafeFromListN :: Int -> [a] -> Deque a Source #
fromListN for a list known to have exactly n elements. O(n). Builds
the levels directly: each gets a prefix of two to nine items and a suffix
of five, and what is between them goes, in nodes of eight, to the level
below. The count is trusted: with more elements than n the suffix
holds them all while the packed count says five, and a later append
writes outside an array.
Queries
toList :: Deque a -> [a] Source #
The elements in order. Lazy: the list is produced as it is consumed.
Taking apart
Whole-sequence transformations (these rebuild the sequence)
intersperse :: a -> Deque a -> Deque a Source #