Safe Haskell	None
Language	Haskell2010

Data.FingerTree.Strict

Contents

Construction
Deconstruction
Transformation
- Maps

Description

Strict variants of FingerTree operations.

Synopsis

data StrictFingerTree v a
fromStrict :: StrictFingerTree v a -> FingerTree v a
forceToStrict :: FingerTree v a -> StrictFingerTree v a
empty :: Measured v a => StrictFingerTree v a
singleton :: Measured v a => a -> StrictFingerTree v a
(<|) :: Measured v a => a -> StrictFingerTree v a -> StrictFingerTree v a
(|>) :: Measured v a => StrictFingerTree v a -> a -> StrictFingerTree v a
(><) :: Measured v a => StrictFingerTree v a -> StrictFingerTree v a -> StrictFingerTree v a
fromList :: Measured v a => [a] -> StrictFingerTree v a
null :: StrictFingerTree v a -> Bool
viewl :: Measured v a => StrictFingerTree v a -> ViewL ( StrictFingerTree v) a
viewr :: Measured v a => StrictFingerTree v a -> ViewR ( StrictFingerTree v) a
data SearchResult v a
- = Position !( StrictFingerTree v a) !a !( StrictFingerTree v a)
- | OnLeft
- | OnRight
- | Nowhere
search :: Measured v a => (v -> v -> Bool ) -> StrictFingerTree v a -> SearchResult v a
split :: Measured v a => (v -> Bool ) -> StrictFingerTree v a -> ( StrictFingerTree v a, StrictFingerTree v a)
takeUntil :: Measured v a => (v -> Bool ) -> StrictFingerTree v a -> StrictFingerTree v a
dropUntil :: Measured v a => (v -> Bool ) -> StrictFingerTree v a -> StrictFingerTree v a
reverse :: Measured v a => StrictFingerTree v a -> StrictFingerTree v a
fmap' :: ( Measured v1 a1, Measured v2 a2) => (a1 -> a2) -> StrictFingerTree v1 a1 -> StrictFingerTree v2 a2
unsafeFmap :: (a -> b) -> StrictFingerTree v a -> StrictFingerTree v b
class Monoid v => Measured v a | a -> v where
- measure :: a -> v
data ViewL (s :: Type -> Type ) a
- = EmptyL
- | a :< (s a)
data ViewR (s :: Type -> Type ) a
- = EmptyR
- | (s a) :> a

Documentation

data StrictFingerTree v a Source #

A newtype wrapper around a FingerTree , representing a finger tree that is strict in its values.

This strictness is not enforced at the type level, but rather by the construction functions in this module. These functions essentially just wrap the original Data.FingerTree functions while forcing the provided value to WHNF.

Instances

Instances details

Measured v a => Measured v ( StrictFingerTree v a) Source #
Instance details Defined in Data.FingerTree.Strict Methods measure :: StrictFingerTree v a -> v Source #
Foldable ( StrictFingerTree v) Source #
Instance details Defined in Data.FingerTree.Strict Methods fold :: Monoid m => StrictFingerTree v m -> m Source # foldMap :: Monoid m => (a -> m) -> StrictFingerTree v a -> m Source # foldMap' :: Monoid m => (a -> m) -> StrictFingerTree v a -> m Source # foldr :: (a -> b -> b) -> b -> StrictFingerTree v a -> b Source # foldr' :: (a -> b -> b) -> b -> StrictFingerTree v a -> b Source # foldl :: (b -> a -> b) -> b -> StrictFingerTree v a -> b Source # foldl' :: (b -> a -> b) -> b -> StrictFingerTree v a -> b Source # foldr1 :: (a -> a -> a) -> StrictFingerTree v a -> a Source # foldl1 :: (a -> a -> a) -> StrictFingerTree v a -> a Source # toList :: StrictFingerTree v a -> [a] Source # null :: StrictFingerTree v a -> Bool Source # length :: StrictFingerTree v a -> Int Source # elem :: Eq a => a -> StrictFingerTree v a -> Bool Source # maximum :: Ord a => StrictFingerTree v a -> a Source # minimum :: Ord a => StrictFingerTree v a -> a Source # sum :: Num a => StrictFingerTree v a -> a Source # product :: Num a => StrictFingerTree v a -> a Source #
Eq a => Eq ( StrictFingerTree v a) Source #
Instance details Defined in Data.FingerTree.Strict Methods (==) :: StrictFingerTree v a -> StrictFingerTree v a -> Bool Source # (/=) :: StrictFingerTree v a -> StrictFingerTree v a -> Bool Source #
Ord a => Ord ( StrictFingerTree v a) Source #
Instance details Defined in Data.FingerTree.Strict Methods compare :: StrictFingerTree v a -> StrictFingerTree v a -> Ordering Source # (<) :: StrictFingerTree v a -> StrictFingerTree v a -> Bool Source # (<=) :: StrictFingerTree v a -> StrictFingerTree v a -> Bool Source # (>) :: StrictFingerTree v a -> StrictFingerTree v a -> Bool Source # (>=) :: StrictFingerTree v a -> StrictFingerTree v a -> Bool Source # max :: StrictFingerTree v a -> StrictFingerTree v a -> StrictFingerTree v a Source # min :: StrictFingerTree v a -> StrictFingerTree v a -> StrictFingerTree v a Source #
Show a => Show ( StrictFingerTree v a) Source #
Instance details Defined in Data.FingerTree.Strict Methods showsPrec :: Int -> StrictFingerTree v a -> ShowS Source # show :: StrictFingerTree v a -> String Source # showList :: [ StrictFingerTree v a] -> ShowS Source #
NoThunks a => NoThunks ( StrictFingerTree v a) Source #
Instance details Defined in Data.FingerTree.Strict Methods noThunks :: Context -> StrictFingerTree v a -> IO ( Maybe ThunkInfo ) Source # wNoThunks :: Context -> StrictFingerTree v a -> IO ( Maybe ThunkInfo ) Source # showTypeOf :: Proxy ( StrictFingerTree v a) -> String Source #

fromStrict :: StrictFingerTree v a -> FingerTree v a Source #

forceToStrict :: FingerTree v a -> StrictFingerTree v a Source #

Convert a FingerTree into a StrictFingerTree by forcing each element to WHNF.

Construction

empty :: Measured v a => StrictFingerTree v a Source #

O(1) . The empty sequence.

singleton :: Measured v a => a -> StrictFingerTree v a Source #

O(1) . A singleton sequence.

(<|) :: Measured v a => a -> StrictFingerTree v a -> StrictFingerTree v a infixr 5 Source #

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 => StrictFingerTree v a -> a -> StrictFingerTree v 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.

(><) :: Measured v a => StrictFingerTree v a -> StrictFingerTree v a -> StrictFingerTree v a infixr 5 Source #

O(log(min(n1,n2))) . Concatenate two sequences.

fromList :: Measured v a => [a] -> StrictFingerTree v a Source #

O(n) . Create a sequence from a finite list of elements. The opposite operation toList is supplied by the Foldable instance.

Deconstruction

null :: StrictFingerTree v a -> Bool Source #

O(1) . Is this the empty sequence?

Examining the ends

viewl :: Measured v a => StrictFingerTree v a -> ViewL ( StrictFingerTree v) a Source #

O(1) . Analyse the left end of a sequence.

viewr :: Measured v a => StrictFingerTree v a -> ViewR ( StrictFingerTree v) a Source #

O(1) . Analyse the right end of a sequence.

Search

data SearchResult v a Source #

A result of search , attempting to find a point where a predicate on splits of the sequence changes from False to True .

Since: 0.1.2.0

Constructors

Position !( StrictFingerTree v a) !a !( StrictFingerTree v a)	A tree opened at a particular element: the prefix to the left, the element, and the suffix to the right.
OnLeft	A position to the left of the sequence, indicating that the predicate is `True` at both ends.
OnRight	A position to the right of the sequence, indicating that the predicate is `False` at both ends.
Nowhere	No position in the tree, returned if the predicate is `True` at the left end and `False` at the right end. This will not occur if the predicate in monotonic on the tree.

Instances

Instances details

Eq a => Eq ( SearchResult v a) Source #
Instance details Defined in Data.FingerTree.Strict Methods (==) :: SearchResult v a -> SearchResult v a -> Bool Source # (/=) :: SearchResult v a -> SearchResult v a -> Bool Source #
Ord a => Ord ( SearchResult v a) Source #
Instance details Defined in Data.FingerTree.Strict Methods compare :: SearchResult v a -> SearchResult v a -> Ordering Source # (<) :: SearchResult v a -> SearchResult v a -> Bool Source # (<=) :: SearchResult v a -> SearchResult v a -> Bool Source # (>) :: SearchResult v a -> SearchResult v a -> Bool Source # (>=) :: SearchResult v a -> SearchResult v a -> Bool Source # max :: SearchResult v a -> SearchResult v a -> SearchResult v a Source # min :: SearchResult v a -> SearchResult v a -> SearchResult v a Source #
Show a => Show ( SearchResult v a) Source #
Instance details Defined in Data.FingerTree.Strict Methods showsPrec :: Int -> SearchResult v a -> ShowS Source # show :: SearchResult v a -> String Source # showList :: [ SearchResult v a] -> ShowS Source #
Generic ( SearchResult v a) Source #
Instance details Defined in Data.FingerTree.Strict Associated Types type Rep ( SearchResult v a) :: Type -> Type Source # Methods from :: SearchResult v a -> Rep ( SearchResult v a) x Source # to :: Rep ( SearchResult v a) x -> SearchResult v a Source #
type Rep ( SearchResult v a) Source #
Instance details Defined in Data.FingerTree.Strict type Rep ( SearchResult v a) = D1 (' MetaData "SearchResult" "Data.FingerTree.Strict" "strict-containers-0.1.0.0-LCiCzdIbvA0LutM86eIzNe" ' False ) (( C1 (' MetaCons "Position" ' PrefixI ' False ) ( S1 (' MetaSel (' Nothing :: Maybe Symbol ) ' NoSourceUnpackedness ' SourceStrict ' DecidedStrict ) ( Rec0 ( StrictFingerTree v a)) :: ( S1 (' MetaSel (' Nothing :: Maybe Symbol ) ' NoSourceUnpackedness ' SourceStrict ' DecidedStrict ) ( Rec0 a) :: S1 (' MetaSel (' Nothing :: Maybe Symbol ) ' NoSourceUnpackedness ' SourceStrict ' DecidedStrict ) ( Rec0 ( StrictFingerTree v a)))) :+: C1 (' MetaCons "OnLeft" ' PrefixI ' False ) ( U1 :: Type -> Type )) :+: ( C1 (' MetaCons "OnRight" ' PrefixI ' False ) ( U1 :: Type -> Type ) :+: C1 (' MetaCons "Nowhere" ' PrefixI ' False ) ( U1 :: Type -> Type )))

search :: Measured v a => (v -> v -> Bool ) -> StrictFingerTree v a -> SearchResult v a Source #

O(log(min(i,n-i))) . Search a sequence for a point where a predicate on splits of the sequence changes from False to True .

The argument p is a relation between the measures of the two sequences that could be appended together to form the sequence t . If the relation is False at the leftmost split and True at the rightmost split, i.e.

not (p mempty (measure t)) && p (measure t) mempty

then there must exist an element x in the sequence such that p is False for the split immediately before x and True for the split just after it:

In this situation, search p t returns such an element x and the pieces l and r of the sequence to its left and right respectively. That is, it returns Position l x r such that

```
l >< (x <| r) = t
```
```
not (p (measure l) (measure (x <| r))
```
```
p (measure (l |> x)) (measure r)
```

For predictable results, one should ensure that there is only one such point, i.e. that the predicate is monotonic on t .

Since: 0.1.2.0

Splitting

These functions are special cases of search .

split :: Measured v a => (v -> Bool ) -> StrictFingerTree v a -> ( StrictFingerTree v a, StrictFingerTree v a) Source #

O(log(min(i,n-i))) . Split a sequence at a point where the predicate on the accumulated 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 .

takeUntil :: Measured v a => (v -> Bool ) -> StrictFingerTree v a -> StrictFingerTree v a Source #

O(log(min(i,n-i))) . Given a monotonic predicate p , takeUntil p t is the largest prefix of t whose measure does not satisfy p .

```
takeUntil p t = fst (split p t)
```

dropUntil :: Measured v a => (v -> Bool ) -> StrictFingerTree v a -> StrictFingerTree v a Source #

O(log(min(i,n-i))) . Given a monotonic predicate p , dropUntil p t is the rest of t after removing the largest prefix whose measure does not satisfy p .

```
dropUntil p t = snd (split p t)
```

Transformation

reverse :: Measured v a => StrictFingerTree v a -> StrictFingerTree v a Source #

O(n) . The reverse of a sequence.

Maps

fmap' :: ( Measured v1 a1, Measured v2 a2) => (a1 -> a2) -> StrictFingerTree v1 a1 -> StrictFingerTree v2 a2 Source #

Like fmap , but with constraints on the element types.

unsafeFmap :: (a -> b) -> StrictFingerTree v a -> StrictFingerTree v b Source #

Like fmap , but safe only if the function preserves the measure.

class Monoid v => Measured v a | a -> v where Source #

Things that can be measured.

Methods

measure :: a -> v Source #

Instances

Instances details

Measured v a => Measured v (Digit a)
Instance details Defined in Data.FingerTree Methods measure :: Digit a -> v Source #
Measured v a => Measured v ( StrictFingerTree v a) Source #
Instance details Defined in Data.FingerTree.Strict Methods measure :: StrictFingerTree v a -> v Source #
Monoid v => Measured v (Node v a)
Instance details Defined in Data.FingerTree Methods measure :: Node v a -> v Source #
Measured v a => Measured v ( FingerTree v a)	O(1) . The cached measure of a tree.
Instance details Defined in Data.FingerTree Methods measure :: FingerTree v a -> v Source #

data ViewL (s :: Type -> Type ) a Source #

View of the left end of a sequence.

Constructors

EmptyL	empty sequence
a :< (s a) infixr 5	leftmost element and the rest of the sequence

Instances

Instances details

Functor s => Functor ( ViewL s)
Instance details Defined in Data.FingerTree Methods fmap :: (a -> b) -> ViewL s a -> ViewL s b Source # (<$) :: a -> ViewL s b -> ViewL s a Source #
( Eq a, Eq (s a)) => Eq ( ViewL s a)
Instance details Defined in Data.FingerTree Methods (==) :: ViewL s a -> ViewL s a -> Bool Source # (/=) :: ViewL s a -> ViewL s a -> Bool Source #
( Ord a, Ord (s a)) => Ord ( ViewL s a)
Instance details Defined in Data.FingerTree Methods compare :: ViewL s a -> ViewL s a -> Ordering Source # (<) :: ViewL s a -> ViewL s a -> Bool Source # (<=) :: ViewL s a -> ViewL s a -> Bool Source # (>) :: ViewL s a -> ViewL s a -> Bool Source # (>=) :: ViewL s a -> ViewL s a -> Bool Source # max :: ViewL s a -> ViewL s a -> ViewL s a Source # min :: ViewL s a -> ViewL s a -> ViewL s a Source #
( Read a, Read (s a)) => Read ( ViewL s a)
Instance details Defined in Data.FingerTree Methods readsPrec :: Int -> ReadS ( ViewL s a) Source # readList :: ReadS [ ViewL s a] Source # readPrec :: ReadPrec ( ViewL s a) Source # readListPrec :: ReadPrec [ ViewL s a] Source #
( Show a, Show (s a)) => Show ( ViewL s a)
Instance details Defined in Data.FingerTree Methods showsPrec :: Int -> ViewL s a -> ShowS Source # show :: ViewL s a -> String Source # showList :: [ ViewL s a] -> ShowS Source #
Generic ( ViewL s a)
Instance details Defined in Data.FingerTree Associated Types type Rep ( ViewL s a) :: Type -> Type Source # Methods from :: ViewL s a -> Rep ( ViewL s a) x Source # to :: Rep ( ViewL s a) x -> ViewL s a Source #
type Rep ( ViewL s a)
Instance details Defined in Data.FingerTree type Rep ( ViewL s a) = D1 (' MetaData "ViewL" "Data.FingerTree" "fingertree-0.1.5.0-9rC7ZsLgw7G1xI3Y5mn8pM" ' False ) ( C1 (' MetaCons "EmptyL" ' PrefixI ' False ) ( U1 :: Type -> Type ) :+: C1 (' MetaCons ":<" (' InfixI ' RightAssociative 5) ' False ) ( S1 (' MetaSel (' Nothing :: Maybe Symbol ) ' NoSourceUnpackedness ' NoSourceStrictness ' DecidedLazy ) ( Rec0 a) :*: S1 (' MetaSel (' Nothing :: Maybe Symbol ) ' NoSourceUnpackedness ' NoSourceStrictness ' DecidedLazy ) ( Rec0 (s a))))

data ViewR (s :: Type -> Type ) a Source #

View of the right end of a sequence.

Constructors

EmptyR	empty sequence
(s a) :> a infixl 5	the sequence minus the rightmost element, and the rightmost element

Instances

Instances details

Functor s => Functor ( ViewR s)
Instance details Defined in Data.FingerTree Methods fmap :: (a -> b) -> ViewR s a -> ViewR s b Source # (<$) :: a -> ViewR s b -> ViewR s a Source #
( Eq a, Eq (s a)) => Eq ( ViewR s a)
Instance details Defined in Data.FingerTree Methods (==) :: ViewR s a -> ViewR s a -> Bool Source # (/=) :: ViewR s a -> ViewR s a -> Bool Source #
( Ord a, Ord (s a)) => Ord ( ViewR s a)
Instance details Defined in Data.FingerTree Methods compare :: ViewR s a -> ViewR s a -> Ordering Source # (<) :: ViewR s a -> ViewR s a -> Bool Source # (<=) :: ViewR s a -> ViewR s a -> Bool Source # (>) :: ViewR s a -> ViewR s a -> Bool Source # (>=) :: ViewR s a -> ViewR s a -> Bool Source # max :: ViewR s a -> ViewR s a -> ViewR s a Source # min :: ViewR s a -> ViewR s a -> ViewR s a Source #
( Read a, Read (s a)) => Read ( ViewR s a)
Instance details Defined in Data.FingerTree Methods readsPrec :: Int -> ReadS ( ViewR s a) Source # readList :: ReadS [ ViewR s a] Source # readPrec :: ReadPrec ( ViewR s a) Source # readListPrec :: ReadPrec [ ViewR s a] Source #
( Show a, Show (s a)) => Show ( ViewR s a)
Instance details Defined in Data.FingerTree Methods showsPrec :: Int -> ViewR s a -> ShowS Source # show :: ViewR s a -> String Source # showList :: [ ViewR s a] -> ShowS Source #
Generic ( ViewR s a)
Instance details Defined in Data.FingerTree Associated Types type Rep ( ViewR s a) :: Type -> Type Source # Methods from :: ViewR s a -> Rep ( ViewR s a) x Source # to :: Rep ( ViewR s a) x -> ViewR s a Source #
type Rep ( ViewR s a)
Instance details Defined in Data.FingerTree type Rep ( ViewR s a) = D1 (' MetaData "ViewR" "Data.FingerTree" "fingertree-0.1.5.0-9rC7ZsLgw7G1xI3Y5mn8pM" ' False ) ( C1 (' MetaCons "EmptyR" ' PrefixI ' False ) ( U1 :: Type -> Type ) :+: C1 (' MetaCons ":>" (' InfixI ' LeftAssociative 5) ' False ) ( S1 (' MetaSel (' Nothing :: Maybe Symbol ) ' NoSourceUnpackedness ' NoSourceStrictness ' DecidedLazy ) ( Rec0 (s a)) :*: S1 (' MetaSel (' Nothing :: Maybe Symbol ) ' NoSourceUnpackedness ' NoSourceStrictness ' DecidedLazy ) ( Rec0 a)))