-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Generic finger-tree structure, with example instances -- -- A general sequence representation with arbitrary annotations, with -- example implementations of various collection types, as described in -- section 4 of -- -- -- -- For a tuned sequence type, see Data.Sequence in the -- containers package, which is a specialization of this -- structure. @package fingertree @version 0.0.1.0 -- | A general sequence representation with arbitrary annotations, for use -- as a base for implementations of various collection types, as -- described in section 4 of -- -- -- -- For a directly usable sequence type, see Data.Sequence, which -- is a specialization of this structure. -- -- An amortized running time is given for each operation, with n -- referring to the length of the sequence. These bounds hold even in a -- persistent (shared) setting. -- -- Note: Many of these operations have the same names as similar -- operations on lists in the Prelude. The ambiguity may be -- resolved using either qualification or the hiding clause. module Data.FingerTree -- | Finger trees with element type a, annotated with measures of -- type v. The operations enforce the constraint -- Measured v a. data FingerTree v a -- | Things that can be measured. class Monoid v => Measured v a | a -> v measure :: Measured v a => a -> v -- | O(1). The empty sequence. empty :: Measured v a => FingerTree v a -- | O(1). A singleton sequence. singleton :: Measured v a => a -> FingerTree v a -- | O(1). Add an element to the left end of a sequence. Mnemonic: a -- triangle with the single element at the pointy end. (<|) :: Measured v a => a -> FingerTree v a -> FingerTree v a -- | O(1). Add an element to the right end of a sequence. Mnemonic: -- a triangle with the single element at the pointy end. (|>) :: Measured v a => FingerTree v a -> a -> FingerTree v a -- | O(log(min(n1,n2))). Concatenate two sequences. (><) :: Measured v a => FingerTree v a -> FingerTree v a -> FingerTree v a -- | O(n). Create a sequence from a finite list of elements. fromList :: Measured v a => [a] -> FingerTree v a -- | O(1). Is this the empty sequence? null :: Measured v a => FingerTree v a -> Bool -- | View of the left end of a sequence. data ViewL s a -- | empty sequence EmptyL :: ViewL s a -- | leftmost element and the rest of the sequence (:<) :: a -> s a -> ViewL s a -- | View of the right end of a sequence. data ViewR s a -- | empty sequence EmptyR :: ViewR s a -- | the sequence minus the rightmost element, and the rightmost element (:>) :: s a -> a -> ViewR s a -- | O(1). Analyse the left end of a sequence. viewl :: Measured v a => FingerTree v a -> ViewL (FingerTree v) a -- | O(1). Analyse the right end of a sequence. viewr :: Measured v a => FingerTree v a -> ViewR (FingerTree v) a -- | O(log(min(i,n-i))). Split a sequence at a point where the -- predicate on the accumulated measure changes from False to -- True. split :: Measured v a => (v -> Bool) -> FingerTree v a -> (FingerTree v a, FingerTree v a) takeUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v a dropUntil :: Measured v a => (v -> Bool) -> FingerTree v a -> FingerTree v a -- | O(n). The reverse of a sequence. reverse :: Measured v a => FingerTree v a -> FingerTree v a -- | Like fmap, but with a more constrained type. fmap' :: (Measured v1 a1, Measured v2 a2) => (a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2 -- | Map all elements of the tree with a function that also takes the -- measure of the prefix of the tree to the left of the element. fmapWithPos :: (Measured v1 a1, Measured v2 a2) => (v1 -> a1 -> a2) -> FingerTree v1 a1 -> FingerTree v2 a2 -- | Like fmap, but safe only if the function preserves the measure. unsafeFmap :: (a -> b) -> FingerTree v a -> FingerTree v b -- | Like traverse, but with a more constrained type. traverse' :: (Measured v1 a1, Measured v2 a2, Applicative f) => (a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2) -- | Traverse the tree with a function that also takes the measure of the -- prefix of the tree to the left of the element. traverseWithPos :: (Measured v1 a1, Measured v2 a2, Applicative f) => (v1 -> a1 -> f a2) -> FingerTree v1 a1 -> f (FingerTree v2 a2) -- | Like traverse, but safe only if the function preserves the -- measure. unsafeTraverse :: Applicative f => (a -> f b) -> FingerTree v a -> f (FingerTree v b) instance (Eq a, Eq (s a)) => Eq (ViewL s a) instance (Ord a, Ord (s a)) => Ord (ViewL s a) instance (Show a, Show (s a)) => Show (ViewL s a) instance (Read a, Read (s a)) => Read (ViewL s a) instance (Eq a, Eq (s a)) => Eq (ViewR s a) instance (Ord a, Ord (s a)) => Ord (ViewR s a) instance (Show a, Show (s a)) => Show (ViewR s a) instance (Read a, Read (s a)) => Read (ViewR s a) instance Show a => Show (Digit a) instance (Show v, Show a) => Show (Node v a) instance (Measured v a, Show a) => Show (FingerTree v a) instance (Measured v a, Ord a) => Ord (FingerTree v a) instance (Measured v a, Eq a) => Eq (FingerTree v a) instance Foldable (FingerTree v) instance Measured v a => Measured v (FingerTree v a) instance Monoid v => Measured v (Node v a) instance Foldable (Node v) instance Measured v a => Measured v (Digit a) instance Foldable Digit instance Measured v a => Monoid (FingerTree v a) instance Functor s => Functor (ViewR s) instance Functor s => Functor (ViewL s) -- | Interval maps implemented using the FingerTree type, following -- section 4.8 of -- -- -- -- An amortized running time is given for each operation, with n -- referring to the size of the priority queue. These bounds hold even in -- a persistent (shared) setting. -- -- Note: Many of these operations have the same names as similar -- operations on lists in the Prelude. The ambiguity may be -- resolved using either qualification or the hiding clause. module Data.IntervalMap.FingerTree -- | A closed interval. The lower bound should be less than or equal to the -- higher bound. data Interval v Interval :: v -> v -> Interval v low :: Interval v -> v high :: Interval v -> v -- | An interval in which the lower and upper bounds are equal. point :: v -> Interval v -- | Map of closed intervals, possibly with duplicates. The Foldable -- and Traversable instances process the intervals in -- lexicographical order. data IntervalMap v a -- | O(1). The empty interval map. empty :: Ord v => IntervalMap v a -- | O(1). Interval map with a single entry. singleton :: Ord v => Interval v -> a -> IntervalMap v a -- | O(log n). Insert an interval into a map. The map may contain -- duplicate intervals; the new entry will be inserted before any -- existing entries for the same interval. insert :: Ord v => Interval v -> a -> IntervalMap v a -> IntervalMap v a -- | O(m log (n/m)). Merge two interval maps. The map may -- contain duplicate intervals; entries with equal intervals are kept in -- the original order. union :: Ord v => IntervalMap v a -> IntervalMap v a -> IntervalMap v a -- | O(k log (n/k)). All intervals that contain the given -- point, in lexicographical order. search :: Ord v => v -> IntervalMap v a -> [(Interval v, a)] -- | O(k log (n/k)). All intervals that intersect with the -- given interval, in lexicographical order. intersections :: Ord v => Interval v -> IntervalMap v a -> [(Interval v, a)] -- | O(k log (n/k)). All intervals that contain the given -- interval, in lexicographical order. dominators :: Ord v => Interval v -> IntervalMap v a -> [(Interval v, a)] instance Eq v => Eq (Interval v) instance Ord v => Ord (Interval v) instance Show v => Show (Interval v) instance Traversable (IntervalMap v) instance Foldable (IntervalMap v) instance Functor (IntervalMap v) instance Ord v => Measured (IntInterval v) (Node v a) instance Ord v => Monoid (IntInterval v) instance Traversable (Node v) instance Foldable (Node v) instance Functor (Node v) -- | Min-priority queues implemented using the FingerTree type, -- following section 4.6 of -- -- -- -- These have the same big-O complexity as skew heap implementations, but -- are approximately an order of magnitude slower. On the other hand, -- they are stable, so they can be used for fair queueing. They are also -- shallower, so that fmap consumes less space. -- -- An amortized running time is given for each operation, with n -- referring to the size of the priority queue. These bounds hold even in -- a persistent (shared) setting. -- -- Note: Many of these operations have the same names as similar -- operations on lists in the Prelude. The ambiguity may be -- resolved using either qualification or the hiding clause. module Data.PriorityQueue.FingerTree -- | Priority queues. data PQueue k v -- | O(1). The empty priority queue. empty :: Ord k => PQueue k v -- | O(1). A singleton priority queue. singleton :: Ord k => k -> v -> PQueue k v -- | O(log(min(n1,n2))). Concatenate two priority queues. -- union is associative, with identity empty. -- -- If there are entries with the same priority in both arguments, -- minView of union xs ys will return those from -- xs before those from ys. union :: Ord k => PQueue k v -> PQueue k v -> PQueue k v -- | O(log n). Add a (priority, value) pair to the front of a -- priority queue. -- -- -- -- If q contains entries with the same priority k, -- minView of insert k v q will return them after -- this one. insert :: Ord k => k -> v -> PQueue k v -> PQueue k v -- | O(log n). Add a (priority, value) pair to the back of a -- priority queue. -- -- -- -- If q contains entries with the same priority k, -- minView of add k v q will return them before -- this one. add :: Ord k => k -> v -> PQueue k v -> PQueue k v -- | O(n). Create a priority queue from a finite list of priorities -- and values. fromList :: Ord k => [(k, v)] -> PQueue k v -- | O(1). Is this the empty priority queue? null :: Ord k => PQueue k v -> Bool -- | O(1) (O(log(n)) for the reduced queue). Returns -- Nothing for an empty map, or the value associated with the -- minimal priority together with the rest of the priority queue. -- -- minView :: Ord k => PQueue k v -> Maybe (v, PQueue k v) -- | O(1) (O(log(n)) for the reduced queue). Returns -- Nothing for an empty map, or the minimal (priority, value) pair -- together with the rest of the priority queue. -- -- minViewWithKey :: Ord k => PQueue k v -> Maybe ((k, v), PQueue k v) instance Ord k => Monoid (PQueue k v) instance Ord k => Foldable (PQueue k) instance Ord k => Functor (PQueue k) instance Ord k => Measured (Prio k v) (Entry k v) instance Ord k => Monoid (Prio k v) instance Foldable (Entry k) instance Functor (Entry k)