Data.Parameterized.Utils.BinTree

Documentation

data MaybeS v

A strict version of Maybe

Constructors

JustS !v

NothingS

Instances

Functor MaybeS

Defined in Data.Parameterized.Utils.BinTree

Methods

fmap :: (a -> b) -> MaybeS a -> MaybeS b

(<$) :: a -> MaybeS b -> MaybeS a

Applicative MaybeS

Defined in Data.Parameterized.Utils.BinTree

Methods

pure :: a -> MaybeS a

(<*>) :: MaybeS (a -> b) -> MaybeS a -> MaybeS b

liftA2 :: (a -> b -> c) -> MaybeS a -> MaybeS b -> MaybeS c

(*>) :: MaybeS a -> MaybeS b -> MaybeS b

(<*) :: MaybeS a -> MaybeS b -> MaybeS a

Alternative MaybeS

Defined in Data.Parameterized.Utils.BinTree

Methods

empty :: MaybeS a

(<|>) :: MaybeS a -> MaybeS a -> MaybeS a

some :: MaybeS a -> MaybeS [a]

many :: MaybeS a -> MaybeS [a]

fromMaybeS :: a -> MaybeS a -> a

data Updated a

Updated a contains a value that has been flagged on whether it was modified by an operation.

Constructors

Updated !a

Unchanged !a

updatedValue :: Updated a -> a

data TreeApp e t

Constructors

BinTree !e !t !t

TipTree

class IsBinTree t e | t -> e where

Methods

asBin :: t -> TreeApp e t

tip :: t

bin :: e -> t -> t -> t

size :: t -> Int

Instances

IsBinTree (MapF k2 a) (Pair k2 a)

Defined in Data.Parameterized.Map

Methods

asBin :: MapF k2 a -> TreeApp (Pair k2 a) (MapF k2 a)

tip :: MapF k2 a

bin :: Pair k2 a -> MapF k2 a -> MapF k2 a -> MapF k2 a

size :: MapF k2 a -> Int

balanceL :: IsBinTree c e => e -> c -> c -> c

balanceL p l r returns a balanced tree for the sequence l ++ [p] ++ r.

It assumes that l and r are close to being balanced, and that only l may contain too many elements.

balanceR :: IsBinTree c e => e -> c -> c -> c

balanceR p l r returns a balanced tree for the sequence l ++ [p] ++ r.

It assumes that l and r are close to being balanced, and that only r may contain too many elements.

glue :: IsBinTree c e => c -> c -> c

glue l r concatenates l and r.

It assumes that l and r are already balanced with respect to each other.

merge :: IsBinTree c e => c -> c -> c

Concatenate two trees that are ordered with respect to each other.

filterGt :: IsBinTree c e => (e -> Ordering) -> c -> MaybeS c

Returns only entries that are less than predicate with respect to the ordering and Nothing if no elements are discarded.

filterLt :: IsBinTree c e => (e -> Ordering) -> c -> MaybeS c

filterLt k m returns submap of m that only contains entries that are smaller than k. If no entries are deleted then return Nothing.

insert :: IsBinTree c e => (e -> e -> Ordering) -> e -> c -> Updated c

insert p m inserts the binding into m. It returns an Unchanged value if the map stays the same size and an updated value if a new entry was inserted.

delete

Arguments

:: IsBinTree c e

=> (e -> Ordering)

Predicate that returns whether the entry is less than, greater than, or equal to the key we are entry that we are looking for.

-> c

-> MaybeS c

union :: IsBinTree c e => (e -> e -> Ordering) -> c -> c -> c

Union two sets

link :: IsBinTree c e => e -> c -> c -> c

link is called to insert a key and value between two disjoint subtrees.

data PairS f s

A Strict pair

Constructors

PairS !f !s