Safe Haskell	None
Language	Haskell2010

Unison.Util.Deque.Internal

Contents

The type
Construction
Queries
Taking apart
Whole-sequence transformations (these rebuild the sequence)
For tests
The parts Rope is built from: digits, nodes, and the

Description

A strict finger tree.

amortized O(1) cons, snoc, uncons, unsnoc when a sequence is used once; O(log n) in the worst case, which a program can hit repeatedly only by going back to the same old version
O(1) size
O(log n) lookup, append, take, drop
no laziness anywhere: every field is strict, nothing is a thunk

The shape is Hinze and Paterson's: a prefix digit, a middle that is a sequence of nodes, a suffix digit. The differences are that the middle is strict, digits hold up to maxD items, and nodes are mostly eight wide. The one invariant is that both digits of a tree with a middle have an item (so the ends, and what is near them, are found without going down). A digit that fills up sheds a node of eight into the middle, and a digit that empties takes a node out of it.

Digits are short lists, so that adding or removing an item at an end allocates one cell or none. A node's children are in an array (or, for the nodes of eight leaves, in the node itself): a node is built once and then only read.

Synopsis

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 ()
data Deque a
- = Nil
- | Deep !Int !(SList a) !(Mid a) !(SList a)
data SList a
- = SNil
- | SCons !a !(SList a)
data Node a
- = N8 !a !a !a !a !a !a !a !a
- | NA !Int !(Arr a)
data Mid a
- = MNil
- | MDeep !Int !Int !(SList (Node a)) !(Mid (Node a)) !(SList (Node a))
type Arr = SmallArray
takeS :: Int -> SList a -> SList a
dropS :: Int -> SList a -> SList a
appendS :: SList a -> SList a -> SList a
lenS :: SList a -> Int
revS :: SList a -> SList a
revOnto :: SList a -> SList a -> SList a
listS :: SList a -> [a]
arr8 :: a -> a -> a -> a -> a -> a -> a -> a -> Arr a
fromSListA :: Int -> SList a -> Arr a
nodeSize :: Node a -> Int
nodeArity :: Node a -> Int
nodeAt :: Int -> Node a -> a
nodeTakeRev :: Int -> Node a -> SList a
nodeDropFwd :: Int -> Node a -> SList a
maxD :: Int
mk :: Int -> Int -> Int -> Int
tsize :: Int -> Int
tpc :: Int -> Int
tsc :: Int -> Int
sizeM :: Mid a -> Int
consM :: Node a -> Mid a -> Mid a
snocM :: Mid a -> Node a -> Mid a
unconsM :: Mid a -> (Node a, Mid a)
unsnocM :: Mid a -> (Mid a, Node a)
scanFwd :: Int -> SList (Node a) -> (Node a, Int)
scanBwd :: Int -> SList (Node a) -> (Node a, Int)
scanKids :: Int -> Node (Node a) -> (Int, Int)
takeM :: Int -> Mid a -> (Mid a, Node a, Int)
dropM :: Int -> Mid a -> (Node a, Int, Mid a)
appM :: Mid a -> Int -> SList (Node a) -> Mid a -> Mid a
foldrM :: (Node a -> r -> r) -> r -> Mid a -> r
foldrS :: (a -> r -> r) -> r -> SList a -> r
foldrRev :: (a -> r -> r) -> r -> SList a -> r
foldrNode :: (a -> r -> r) -> Node a -> r -> r
foldlM :: (r -> Node a -> r) -> r -> Mid a -> r
foldlS :: (r -> a -> r) -> r -> SList a -> r
foldlRev :: (r -> a -> r) -> r -> SList a -> r
foldlNode :: (r -> a -> r) -> r -> Node a -> r
validM :: Int -> (a -> Either String Int) -> Mid a -> Either String Int

The type

type Seq = Deque Source #

pattern Empty :: Deque a Source #

pattern (:<|) :: a -> Deque a -> Deque a infixr 5 Source #

pattern (:|>) :: Deque a -> a -> Deque a infixl 5 Source #

Construction

empty :: Deque a Source #

singleton :: a -> Deque a Source #

cons :: a -> Deque a -> Deque a Source #

snoc :: Deque a -> a -> Deque a Source #

append :: Deque a -> Deque a -> Deque a Source #

(<|) :: a -> Deque a -> Deque a infixr 5 Source #

(|>) :: Deque a -> a -> Deque a infixl 5 Source #

(><) :: Deque a -> Deque a -> Deque a infixr 5 Source #

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.

fromFunction :: Int -> (Int -> a) -> Deque a Source #

fromFunction n f is f 0, f 1, ..., f (n - 1).