| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.FingerTree.RootMeasured.Strict
Synopsis
- data StrictFingerTree vr vi a
- class Monoid v => Measured v a | a -> v where
- measure :: a -> v
- class (LeftCancellative v, RightCancellative v, Monoid v) => RootMeasured v a | a -> v where
- measureRoot :: a -> v
- type SuperMeasured vr vi a = (RootMeasured vr a, Measured vi a)
- fromList :: SuperMeasured vr vi a => [a] -> StrictFingerTree vr vi a
- (|>) :: SuperMeasured vr vi a => StrictFingerTree vr vi a -> a -> StrictFingerTree vr vi a
- class Sized a where
- newtype SplitRootMeasure vr vi a = SplitRootMeasure {
- unSplitRootMeasure :: vr -> (StrictFingerTree vi a, StrictFingerTree vi a) -> (vr, vr)
- split :: SuperMeasured vr vi a => (vi -> Bool) -> SplitRootMeasure vr vi a -> StrictFingerTree vr vi a -> (StrictFingerTree vr vi a, StrictFingerTree vr vi a)
- splitSized :: (SuperMeasured vr vi a, Sized vi) => (vi -> Bool) -> StrictFingerTree vr vi a -> (StrictFingerTree vr vi a, StrictFingerTree vr vi a)
- splitl :: SuperMeasured vr vi a => (vi -> Bool) -> StrictFingerTree vr vi a -> (StrictFingerTree vr vi a, StrictFingerTree vr vi a)
- splitr :: SuperMeasured vr vi a => (vi -> Bool) -> StrictFingerTree vr vi a -> (StrictFingerTree vr vi a, StrictFingerTree vr vi a)
- fmap' :: (SuperMeasured vr1 vi1 a1, SuperMeasured vr2 vi2 a2) => (a1 -> a2) -> StrictFingerTree vr1 vi1 a1 -> StrictFingerTree vr2 vi2 a2
- fmap'' :: (SuperMeasured vr1 vi1 a1, SuperMeasured vr2 vi2 a2) => (a1 -> a2) -> (vr1 -> vr2) -> StrictFingerTree vr1 vi1 a1 -> StrictFingerTree vr2 vi2 a2
Strict finger trees with root measures
data StrictFingerTree vr vi a Source #
A StrictFingerTree with elements of type a, an internal measure of type
vi, and a root measure of type vr.
Instances
Measuring
class Monoid v => Measured v a | a -> v where #
Things that can be measured.
Instances
| Measured v a => Measured v (Digit a) | |
Defined in Data.FingerTree | |
| Measured v a => Measured v (StrictFingerTree v a) | |
Defined in Data.FingerTree.Strict Methods measure :: StrictFingerTree v a -> v # | |
| Measured v a => Measured v (FingerTree v a) | O(1). The cached measure of a tree. |
Defined in Data.FingerTree Methods measure :: FingerTree v a -> v # | |
| Monoid v => Measured v (Node v a) | |
Defined in Data.FingerTree | |
| Measured vi a => Measured vi (StrictFingerTree vr vi a) Source # | All |
Defined in Data.FingerTree.RootMeasured.Strict Methods measure :: StrictFingerTree vr vi a -> vi # | |
class (LeftCancellative v, RightCancellative v, Monoid v) => RootMeasured v a | a -> v where Source #
Re-iteration of Measured
This re-iteration is necessary because we want to allow the root measure to
be distinct from the internal measure. For example, we can not create both of
these instances for distinct types T and T':
instance Measured T a where -- ...
instance Measured T' a where -- ...
Furthermore, we want the root measure to be a cancellative monoid.
Methods
measureRoot :: a -> v Source #
Instances
| RootMeasured vr a => RootMeasured vr (StrictFingerTree vr vi a) Source # | All |
Defined in Data.FingerTree.RootMeasured.Strict Methods measureRoot :: StrictFingerTree vr vi a -> vr Source # | |
type SuperMeasured vr vi a = (RootMeasured vr a, Measured vi a) Source #
Conjunction of RootMeasuredMeasured
Construction
fromList :: SuperMeasured vr vi a => [a] -> StrictFingerTree vr vi a Source #
(|>) :: SuperMeasured vr vi a => StrictFingerTree vr vi a -> a -> StrictFingerTree vr vi a infixl 5 Source #
O(1). Add an element to the right end of a sequence.
Mnemonic: a triangle with the single element at the pointy end.
Splitting
newtype SplitRootMeasure vr vi a Source #
A function that computes the root measures of the left and right parts of a split.
The function's arguments are: * The root measure of the input of the split function, and * The left and right parts of the split.
Constructors
| SplitRootMeasure | |
Fields
| |
split :: SuperMeasured vr vi a => (vi -> Bool) -> SplitRootMeasure vr vi a -> StrictFingerTree vr vi a -> (StrictFingerTree vr vi a, StrictFingerTree vr vi a) Source #
O(log(min(i,n-i))) + O(f(l, r)). Split a sequence at a point where the
predicate on the accumulated internal measure of the prefix changes from
False to True.
For predictable results, one should ensure that there is only one such point, i.e. that the predicate is monotonic.
A SplitRootMeasuref should be provided that computes the root
measures of the left and right parts of the split. Since the vr type is a
cancellative monoid, we can use stripPrefix and stripSuffix to compute
the root measures: see splitlsplitr
Note on time complexity: the log factor comes from splitlog factor of the time complexity is determined by the smallest part of
the split: the result of (min(i, n-i)) is either i or n-i, which are
the lengths of the split parts.
Denotations for time complexity: n denotes the length of the input of the
split. i denotes the length of left part of the split result. l denotes
the left part of the split result. r denotes the right part of the split
result. f denotes a SplitRootMeasurelength denotes a
function that computes the length of a finger tree.
splitSized :: (SuperMeasured vr vi a, Sized vi) => (vi -> Bool) -> StrictFingerTree vr vi a -> (StrictFingerTree vr vi a, StrictFingerTree vr vi a) Source #
O(log(min(i,n-i))) + O(min(i,n-i)). Specialisation of spliti or n-i is smallest.
Note: a way to view splitSizedsplitlsplitri or n-i are
smallest respectively.
splitl :: SuperMeasured vr vi a => (vi -> Bool) -> StrictFingerTree vr vi a -> (StrictFingerTree vr vi a, StrictFingerTree vr vi a) Source #
O(log(min(i,n-i))) + O(i). Specialisation of spliti is small.
splitr :: SuperMeasured vr vi a => (vi -> Bool) -> StrictFingerTree vr vi a -> (StrictFingerTree vr vi a, StrictFingerTree vr vi a) Source #
O(log(min(i,n-i))) + O(n-i). Specialisation of spliti is large.
Maps
fmap' :: (SuperMeasured vr1 vi1 a1, SuperMeasured vr2 vi2 a2) => (a1 -> a2) -> StrictFingerTree vr1 vi1 a1 -> StrictFingerTree vr2 vi2 a2 Source #
Like fmap
Note: vr2 is reconstructed in time linear in the size of the finger tree.
fmap'' :: (SuperMeasured vr1 vi1 a1, SuperMeasured vr2 vi2 a2) => (a1 -> a2) -> (vr1 -> vr2) -> StrictFingerTree vr1 vi1 a1 -> StrictFingerTree vr2 vi2 a2 Source #