Module

Data.FingerTree

Package: purescript-sequences
Repository: hdgarrood/purescript-sequences

This module defines a general-purpose data structure, known as a "finger tree", which is intended to be used as a building block for implementing other data structures. See, for example, Seq from Data.Sequence.

#Node Source

data Node v a

Constructors

Node2 v a a
Node3 v a a a

Instances

(Show a, Show v) => Show (Node v a)
Functor (Node v)
Foldable (Node v)
Traversable (Node v)
Measured (Node v a) v

#node2 Source

node2 :: forall v a. Monoid v => Measured a v => a -> a -> Node v a

#node3 Source

node3 :: forall v a. Monoid v => Measured a v => a -> a -> a -> Node v a

#nodeToDigit Source

nodeToDigit :: forall v a. Node v a -> Digit a

#FingerTree Source

data FingerTree v a

Constructors

Empty
Single a
Deep (Lazy v) (Digit a) (Lazy (FingerTree v (Node v a))) (Digit a)

Instances

(Show v, Show a) => Show (FingerTree v a)
(Monoid v, Measured a v) => Semigroup (FingerTree v a)
Functor (FingerTree v)
Foldable (FingerTree v)
Traversable (FingerTree v)
(Monoid v, Measured a v) => Measured (FingerTree v a) v

#lazyEmpty Source

lazyEmpty :: forall a v. Lazy (FingerTree v a)

#deep Source

deep :: forall v a. Monoid v => Measured a v => Digit a -> Lazy (FingerTree v (Node v a)) -> Digit a -> FingerTree v a

#eqFingerTree Source

eqFingerTree :: forall v a. Monoid v => Measured a v => Eq a => FingerTree v a -> FingerTree v a -> Boolean

#compareFingerTree Source

compareFingerTree :: forall v a. Monoid v => Measured a v => Ord a => FingerTree v a -> FingerTree v a -> Ordering

#cons Source

cons :: forall v a. Monoid v => Measured a v => a -> FingerTree v a -> FingerTree v a

#snoc Source

snoc :: forall v a. Monoid v => Measured a v => FingerTree v a -> a -> FingerTree v a

#consAll Source

consAll :: forall v a f. Monoid v => Measured a v => Foldable f => f a -> FingerTree v a -> FingerTree v a

#snocAll Source

snocAll :: forall v a f. Monoid v => Measured a v => Foldable f => FingerTree v a -> f a -> FingerTree v a

#toFingerTree Source

toFingerTree :: forall v a f. Monoid v => Measured a v => Foldable f => f a -> FingerTree v a

#ViewL Source

data ViewL s a

Constructors

NilL
ConsL a (Lazy (s a))

Instances

(Functor s) => Functor (ViewL s)

#viewL Source

viewL :: forall v a. Monoid v => Measured a v => FingerTree v a -> ViewL (FingerTree v) a

#deepL Source

deepL :: forall v a. Monoid v => Measured a v => Array a -> Lazy (FingerTree v (Node v a)) -> Digit a -> FingerTree v a

#isEmpty Source

isEmpty :: forall v a. Monoid v => Measured a v => FingerTree v a -> Boolean

#head Source

head :: forall v a. Monoid v => Measured a v => FingerTree v a -> Maybe a

#tail Source

tail :: forall v a. Monoid v => Measured a v => FingerTree v a -> Maybe (FingerTree v a)

#ViewR Source

data ViewR s a

Constructors

NilR
SnocR (Lazy (s a)) a

#viewR Source

viewR :: forall v a. Monoid v => Measured a v => FingerTree v a -> ViewR (FingerTree v) a

#deepR Source

deepR :: forall v a. Monoid v => Measured a v => Digit a -> Lazy (FingerTree v (Node v a)) -> Array a -> FingerTree v a

#last Source

last :: forall v a. Monoid v => Measured a v => FingerTree v a -> Maybe a

#init Source

init :: forall v a. Monoid v => Measured a v => FingerTree v a -> Maybe (FingerTree v a)

#app3 Source

app3 :: forall v a. Monoid v => Measured a v => FingerTree v a -> Array a -> FingerTree v a -> FingerTree v a

#nodes Source

nodes :: forall v a. Monoid v => Measured a v => Array a -> Array (Node v a)

#append Source

append :: forall v a. Monoid v => Measured a v => FingerTree v a -> FingerTree v a -> FingerTree v a

#Split Source

data Split f a

Constructors

Split (f a) a (f a)

#LazySplit Source

data LazySplit f a

Constructors

LazySplit (Lazy (f a)) a (Lazy (f a))

#splitDigit Source

splitDigit :: forall v a. Monoid v => Measured a v => (v -> Boolean) -> v -> Digit a -> Split Array a

#splitTree Source

splitTree :: forall v a. Monoid v => Measured a v => Partial => (v -> Boolean) -> v -> FingerTree v a -> LazySplit (FingerTree v) a

This function throws an error if the argument is empty.

#split Source

split :: forall v a. Monoid v => Measured a v => Partial => (v -> Boolean) -> FingerTree v a -> Tuple (Lazy (FingerTree v a)) (Lazy (FingerTree v a))

Split a finger tree according to which elements satisfy a predicate. This function is partial because it requires that the result of applying the predicate to mempty is false; if this is not the case, the behaviour is undefined.

#filter Source

filter :: forall v a. Monoid v => Measured a v => (a -> Boolean) -> FingerTree v a -> FingerTree v a

#unfoldLeft Source

unfoldLeft :: forall v a f. Unfoldable f => Monoid v => Measured a v => FingerTree v a -> f a

#unfoldRight Source

unfoldRight :: forall v a f. Unfoldable f => Monoid v => Measured a v => FingerTree v a -> f a

#fullyForce Source

fullyForce :: forall v a. FingerTree v a -> FingerTree v a

Re-exports from Data.FingerTree.Digit

#Digit Source

newtype Digit a

A Digit is just an array which has between one and four elements (inclusive). If a Digit has two or three elements, it is described as 'safe'; otherwise, it is described as 'dangerous'.

Instances

Functor Digit
(Show a) => Show (Digit a)
Foldable Digit
Traversable Digit
(Monoid v, Measured a v) => Measured (Digit a) v

#unsafeIndex Source

unsafeIndex :: forall a. Partial => Digit a -> Int -> a

#tailDigit Source

tailDigit :: forall a. Digit a -> Array a

#snocDigit Source

snocDigit :: forall a. Partial => Digit a -> a -> Digit a

Append a single element. This is partial because the result is not defined in the case where the argument has 4 elements.

#runDigit Source

runDigit :: forall a. Digit a -> Array a

#mkDigitMay Source

mkDigitMay :: forall a. Array a -> Maybe (Digit a)

Like mkDigit, except this returns Nothing on invalid input.

#mkDigit3 Source

mkDigit3 :: forall a. a -> a -> a -> Digit a

#mkDigit2 Source

mkDigit2 :: forall a. a -> a -> Digit a

#mkDigit1 Source

mkDigit1 :: forall a. a -> Digit a

#mkDigit Source

mkDigit :: forall a. Partial => Array a -> Digit a

This function is only defined when the argument has between one and four elements inclusive. It will not throw an error if this is not satisfied, although the Digit length invariant will be violated, which will cause other functions to break.

#lastDigit Source

lastDigit :: forall a. Digit a -> a

#initDigit Source

initDigit :: forall a. Digit a -> Array a

#headDigit Source

headDigit :: forall a. Digit a -> a

#dropDigit Source

dropDigit :: forall a. Int -> Digit a -> Array a

#digitLength Source

digitLength :: forall a. Digit a -> Int

#consDigit Source

consDigit :: forall a. Partial => a -> Digit a -> Digit a

Prepend a single element. This is partial because the result is not defined in the case where the argument has 4 elements.

#(!) Source

Operator alias for Data.FingerTree.Digit.unsafeIndex (non-associative / precedence 2)

Modules: Data.FingerTree; Data.FingerTree.Digit; Data.Sequence; Data.Sequence.Internal; Data.Sequence.NonEmpty; Data.Sequence.Ordered