libghc-fingertree-doc 0.1.1.0-5 / usr / share / doc / libghc-fingertree-doc / html / fingertree.txt

-- 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, for use
--   as a base for implementations of various collection types, with
--   examples, as described in section 4 of
--   
--   <ul>
--   <li>Ralf Hinze and Ross Paterson, "Finger trees: a simple
--   general-purpose data structure", <i>Journal of Functional
--   Programming</i> 16:2 (2006) pp 197-217.
--   <a>http://staff.city.ac.uk/~ross/papers/FingerTree.html</a></li>
--   </ul>
--   
--   For a tuned sequence type, see <tt>Data.Sequence</tt> in the
--   <tt>containers</tt> package, which is a specialization of this
--   structure.
@package fingertree
@version 0.1.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
--   
--   <ul>
--   <li>Ralf Hinze and Ross Paterson, "Finger trees: a simple
--   general-purpose data structure", <i>Journal of Functional
--   Programming</i> 16:2 (2006) pp 197-217.
--   <a>http://staff.city.ac.uk/~ross/papers/FingerTree.html</a></li>
--   </ul>
--   
--   For a directly usable sequence type, see <tt>Data.Sequence</tt>, which
--   is a specialization of this structure.
--   
--   An amortized running time is given for each operation, with <i>n</i>
--   referring to the length of the sequence. These bounds hold even in a
--   persistent (shared) setting.
--   
--   <i>Note</i>: Many of these operations have the same names as similar
--   operations on lists in the <a>Prelude</a>. The ambiguity may be
--   resolved using either qualification or the <tt>hiding</tt> clause.
module Data.FingerTree

-- | A representation of a sequence of values of type <tt>a</tt>, allowing
--   access to the ends in constant time, and append and split in time
--   logarithmic in the size of the smaller piece.
--   
--   The collection is also parameterized by a measure type <tt>v</tt>,
--   which is used to specify a position in the sequence for the
--   <a>split</a> operation. The types of the operations enforce the
--   constraint <tt><a>Measured</a> v a</tt>, which also implies that the
--   type <tt>v</tt> is determined by <tt>a</tt>.
--   
--   A variety of abstract data types can be implemented by using different
--   element types and measurements.
data FingerTree v a

-- | Things that can be measured.
class (Monoid v) => Measured v a | a -> v
measure :: Measured v a => a -> v

-- | <i>O(1)</i>. The empty sequence.
empty :: Measured v a => FingerTree v a

-- | <i>O(1)</i>. A singleton sequence.
singleton :: Measured v a => a -> FingerTree v a

-- | <i>O(1)</i>. 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
infixr 5 <|

-- | <i>O(1)</i>. 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
infixl 5 |>

-- | <i>O(log(min(n1,n2)))</i>. Concatenate two sequences.
(><) :: (Measured v a) => FingerTree v a -> FingerTree v a -> FingerTree v a
infixr 5 ><

-- | <i>O(n)</i>. Create a sequence from a finite list of elements.
fromList :: (Measured v a) => [a] -> FingerTree v a

-- | <i>O(1)</i>. 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

-- | <i>O(1)</i>. Analyse the left end of a sequence.
viewl :: (Measured v a) => FingerTree v a -> ViewL (FingerTree v) a

-- | <i>O(1)</i>. Analyse the right end of a sequence.
viewr :: (Measured v a) => FingerTree v a -> ViewR (FingerTree v) a

-- | <i>O(log(min(i,n-i)))</i>. Split a sequence at a point where the
--   predicate on the accumulated measure changes from <a>False</a> to
--   <a>True</a>.
--   
--   For predictable results, one should ensure that there is only one such
--   point, i.e. that the predicate is <i>monotonic</i>.
split :: (Measured v a) => (v -> Bool) -> FingerTree v a -> (FingerTree v a, FingerTree v a)

-- | <i>O(log(min(i,n-i)))</i>. Given a monotonic predicate <tt>p</tt>,
--   <tt><a>takeUntil</a> p t</tt> is the largest prefix of <tt>t</tt>
--   whose measure does not satisfy <tt>p</tt>.
--   
--   <ul>
--   <li><pre><a>takeUntil</a> p t = <a>fst</a> (<a>split</a> p
--   t)</pre></li>
--   </ul>
takeUntil :: (Measured v a) => (v -> Bool) -> FingerTree v a -> FingerTree v a

-- | <i>O(log(min(i,n-i)))</i>. Given a monotonic predicate <tt>p</tt>,
--   <tt><a>dropUntil</a> p t</tt> is the rest of <tt>t</tt> after removing
--   the largest prefix whose measure does not satisfy <tt>p</tt>.
--   
--   <ul>
--   <li><pre><a>dropUntil</a> p t = <a>snd</a> (<a>split</a> p
--   t)</pre></li>
--   </ul>
dropUntil :: (Measured v a) => (v -> Bool) -> FingerTree v a -> FingerTree v a

-- | <i>O(n)</i>. The reverse of a sequence.
reverse :: (Measured v a) => FingerTree v a -> FingerTree v a

-- | Like <a>fmap</a>, 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 <a>fmap</a>, but safe only if the function preserves the measure.
unsafeFmap :: (a -> b) -> FingerTree v a -> FingerTree v b

-- | Like <a>traverse</a>, 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 <a>traverse</a>, but safe only if the function preserves the
--   measure.
unsafeTraverse :: (Applicative f) => (a -> f b) -> FingerTree v a -> f (FingerTree v b)
instance (GHC.Show.Show v, GHC.Show.Show a) => GHC.Show.Show (Data.FingerTree.Node v a)
instance GHC.Show.Show a => GHC.Show.Show (Data.FingerTree.Digit a)
instance (GHC.Read.Read a, GHC.Read.Read (s a)) => GHC.Read.Read (Data.FingerTree.ViewR s a)
instance (GHC.Show.Show a, GHC.Show.Show (s a)) => GHC.Show.Show (Data.FingerTree.ViewR s a)
instance (GHC.Classes.Ord a, GHC.Classes.Ord (s a)) => GHC.Classes.Ord (Data.FingerTree.ViewR s a)
instance (GHC.Classes.Eq a, GHC.Classes.Eq (s a)) => GHC.Classes.Eq (Data.FingerTree.ViewR s a)
instance (GHC.Read.Read a, GHC.Read.Read (s a)) => GHC.Read.Read (Data.FingerTree.ViewL s a)
instance (GHC.Show.Show a, GHC.Show.Show (s a)) => GHC.Show.Show (Data.FingerTree.ViewL s a)
instance (GHC.Classes.Ord a, GHC.Classes.Ord (s a)) => GHC.Classes.Ord (Data.FingerTree.ViewL s a)
instance (GHC.Classes.Eq a, GHC.Classes.Eq (s a)) => GHC.Classes.Eq (Data.FingerTree.ViewL s a)
instance GHC.Base.Functor s => GHC.Base.Functor (Data.FingerTree.ViewL s)
instance GHC.Base.Functor s => GHC.Base.Functor (Data.FingerTree.ViewR s)
instance Data.FingerTree.Measured v a => GHC.Base.Monoid (Data.FingerTree.FingerTree v a)
instance Data.Foldable.Foldable Data.FingerTree.Digit
instance Data.FingerTree.Measured v a => Data.FingerTree.Measured v (Data.FingerTree.Digit a)
instance Data.Foldable.Foldable (Data.FingerTree.Node v)
instance GHC.Base.Monoid v => Data.FingerTree.Measured v (Data.FingerTree.Node v a)
instance Data.FingerTree.Measured v a => Data.FingerTree.Measured v (Data.FingerTree.FingerTree v a)
instance Data.Foldable.Foldable (Data.FingerTree.FingerTree v)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.FingerTree.FingerTree v a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.FingerTree.FingerTree v a)
instance GHC.Show.Show a => GHC.Show.Show (Data.FingerTree.FingerTree v a)


-- | Interval maps implemented using the <a>FingerTree</a> type, following
--   section 4.8 of
--   
--   <ul>
--   <li>Ralf Hinze and Ross Paterson, "Finger trees: a simple
--   general-purpose data structure", <i>Journal of Functional
--   Programming</i> 16:2 (2006) pp 197-217.
--   <a>http://staff.city.ac.uk/~ross/papers/FingerTree.html</a></li>
--   </ul>
--   
--   An amortized running time is given for each operation, with <i>n</i>
--   referring to the size of the priority queue. These bounds hold even in
--   a persistent (shared) setting.
--   
--   <i>Note</i>: Many of these operations have the same names as similar
--   operations on lists in the <a>Prelude</a>. The ambiguity may be
--   resolved using either qualification or the <tt>hiding</tt> 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 <a>Foldable</a>
--   and <a>Traversable</a> instances process the intervals in
--   lexicographical order.
data IntervalMap v a

-- | <i>O(1)</i>. The empty interval map.
empty :: (Ord v) => IntervalMap v a

-- | <i>O(1)</i>. Interval map with a single entry.
singleton :: (Ord v) => Interval v -> a -> IntervalMap v a

-- | <i>O(log n)</i>. 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

-- | <i>O(m log (n</i>/<i>m))</i>. 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

-- | <i>O(k log (n</i>/<i>k))</i>. All intervals that contain the given
--   point, in lexicographical order.
search :: (Ord v) => v -> IntervalMap v a -> [(Interval v, a)]

-- | <i>O(k log (n</i>/<i>k))</i>. All intervals that intersect with the
--   given interval, in lexicographical order.
intersections :: (Ord v) => Interval v -> IntervalMap v a -> [(Interval v, a)]

-- | <i>O(k log (n</i>/<i>k))</i>. All intervals that contain the given
--   interval, in lexicographical order.
dominators :: (Ord v) => Interval v -> IntervalMap v a -> [(Interval v, a)]
instance GHC.Show.Show v => GHC.Show.Show (Data.IntervalMap.FingerTree.Interval v)
instance GHC.Classes.Ord v => GHC.Classes.Ord (Data.IntervalMap.FingerTree.Interval v)
instance GHC.Classes.Eq v => GHC.Classes.Eq (Data.IntervalMap.FingerTree.Interval v)
instance GHC.Base.Functor (Data.IntervalMap.FingerTree.Node v)
instance Data.Foldable.Foldable (Data.IntervalMap.FingerTree.Node v)
instance Data.Traversable.Traversable (Data.IntervalMap.FingerTree.Node v)
instance GHC.Classes.Ord v => GHC.Base.Monoid (Data.IntervalMap.FingerTree.IntInterval v)
instance GHC.Classes.Ord v => Data.FingerTree.Measured (Data.IntervalMap.FingerTree.IntInterval v) (Data.IntervalMap.FingerTree.Node v a)
instance GHC.Base.Functor (Data.IntervalMap.FingerTree.IntervalMap v)
instance Data.Foldable.Foldable (Data.IntervalMap.FingerTree.IntervalMap v)
instance Data.Traversable.Traversable (Data.IntervalMap.FingerTree.IntervalMap v)
instance GHC.Classes.Ord v => GHC.Base.Monoid (Data.IntervalMap.FingerTree.IntervalMap v a)


-- | Min-priority queues implemented using the <a>FingerTree</a> type,
--   following section 4.6 of
--   
--   <ul>
--   <li>Ralf Hinze and Ross Paterson, "Finger trees: a simple
--   general-purpose data structure", <i>Journal of Functional
--   Programming</i> 16:2 (2006) pp 197-217.
--   <a>http://staff.city.ac.uk/~ross/papers/FingerTree.html</a></li>
--   </ul>
--   
--   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 <a>fmap</a> consumes less space.
--   
--   An amortized running time is given for each operation, with <i>n</i>
--   referring to the size of the priority queue. These bounds hold even in
--   a persistent (shared) setting.
--   
--   <i>Note</i>: Many of these operations have the same names as similar
--   operations on lists in the <a>Prelude</a>. The ambiguity may be
--   resolved using either qualification or the <tt>hiding</tt> clause.
module Data.PriorityQueue.FingerTree

-- | Priority queues.
data PQueue k v

-- | <i>O(1)</i>. The empty priority queue.
empty :: Ord k => PQueue k v

-- | <i>O(1)</i>. A singleton priority queue.
singleton :: Ord k => k -> v -> PQueue k v

-- | <i>O(log(min(n1,n2)))</i>. Concatenate two priority queues.
--   <a>union</a> is associative, with identity <a>empty</a>.
--   
--   If there are entries with the same priority in both arguments,
--   <a>minView</a> of <tt><a>union</a> xs ys</tt> will return those from
--   <tt>xs</tt> before those from <tt>ys</tt>.
union :: Ord k => PQueue k v -> PQueue k v -> PQueue k v

-- | <i>O(log n)</i>. Add a (priority, value) pair to the front of a
--   priority queue.
--   
--   <ul>
--   <li><pre><a>insert</a> k v q = <a>union</a> (<a>singleton</a> k v)
--   q</pre></li>
--   </ul>
--   
--   If <tt>q</tt> contains entries with the same priority <tt>k</tt>,
--   <a>minView</a> of <tt><a>insert</a> k v q</tt> will return them after
--   this one.
insert :: Ord k => k -> v -> PQueue k v -> PQueue k v

-- | <i>O(log n)</i>. Add a (priority, value) pair to the back of a
--   priority queue.
--   
--   <ul>
--   <li><pre><a>add</a> k v q = <a>union</a> q (<a>singleton</a> k
--   v)</pre></li>
--   </ul>
--   
--   If <tt>q</tt> contains entries with the same priority <tt>k</tt>,
--   <a>minView</a> of <tt><a>add</a> k v q</tt> will return them before
--   this one.
add :: Ord k => k -> v -> PQueue k v -> PQueue k v

-- | <i>O(n)</i>. Create a priority queue from a finite list of priorities
--   and values.
fromList :: Ord k => [(k, v)] -> PQueue k v

-- | <i>O(1)</i>. Is this the empty priority queue?
null :: Ord k => PQueue k v -> Bool

-- | <i>O(1)</i> for the element, <i>O(log(n))</i> for the reduced queue.
--   Returns <a>Nothing</a> for an empty map, or the value associated with
--   the minimal priority together with the rest of the priority queue.
--   
--   <ul>
--   <li><pre><a>minView</a> <a>empty</a> = <a>Nothing</a></pre></li>
--   <li><pre><a>minView</a> (<a>singleton</a> k v) = <a>Just</a> (v,
--   <a>empty</a>)</pre></li>
--   </ul>
minView :: Ord k => PQueue k v -> Maybe (v, PQueue k v)

-- | <i>O(1)</i> for the element, <i>O(log(n))</i> for the reduced queue.
--   Returns <a>Nothing</a> for an empty map, or the minimal (priority,
--   value) pair together with the rest of the priority queue.
--   
--   <ul>
--   <li><pre><a>minViewWithKey</a> <a>empty</a> =
--   <a>Nothing</a></pre></li>
--   <li><pre><a>minViewWithKey</a> (<a>singleton</a> k v) = <a>Just</a>
--   ((k, v), <a>empty</a>)</pre></li>
--   <li>If <tt><a>minViewWithKey</a> qi = <a>Just</a> ((ki, vi), qi')</tt>
--   and <tt>k1 &lt;= k2</tt>, then <tt><a>minViewWithKey</a> (<a>union</a>
--   q1 q2) = <a>Just</a> ((k1, v1), <a>union</a> q1' q2)</tt></li>
--   <li>If <tt><a>minViewWithKey</a> qi = <a>Just</a> ((ki, vi), qi')</tt>
--   and <tt>k2 &lt; k1</tt>, then <tt><a>minViewWithKey</a> (<a>union</a>
--   q1 q2) = <a>Just</a> ((k2, v2), <a>union</a> q1 q2')</tt></li>
--   </ul>
minViewWithKey :: Ord k => PQueue k v -> Maybe ((k, v), PQueue k v)
instance GHC.Base.Functor (Data.PriorityQueue.FingerTree.Entry k)
instance Data.Foldable.Foldable (Data.PriorityQueue.FingerTree.Entry k)
instance GHC.Classes.Ord k => GHC.Base.Monoid (Data.PriorityQueue.FingerTree.Prio k v)
instance GHC.Classes.Ord k => Data.FingerTree.Measured (Data.PriorityQueue.FingerTree.Prio k v) (Data.PriorityQueue.FingerTree.Entry k v)
instance GHC.Classes.Ord k => GHC.Base.Functor (Data.PriorityQueue.FingerTree.PQueue k)
instance GHC.Classes.Ord k => Data.Foldable.Foldable (Data.PriorityQueue.FingerTree.PQueue k)
instance GHC.Classes.Ord k => GHC.Base.Monoid (Data.PriorityQueue.FingerTree.PQueue k v)