parameterized-utils-2.1.11.0: Classes and data structures for working with data-kind indexed types

Copyright | (c) Galois Inc 2014-2019
Maintainer | Joe Hendrix <jhendrix@galois.com>
Safe Haskell | Safe
Language | Haskell2010

Data.Parameterized.Utils.BinTree

Description

Synopsis

- data MaybeS v
  - = JustS !v
  - | NothingS
- fromMaybeS :: a -> MaybeS a -> a
- data Updated a
  - = Updated !a
  - | Unchanged !a
- updatedValue :: Updated a -> a
- data TreeApp e t
  - = BinTree !e !t !t
  - | TipTree
- class IsBinTree t e | t -> e where
  - asBin :: t -> TreeApp e t
  - tip :: t
  - bin :: e -> t -> t -> t
  - size :: t -> Int
- balanceL :: IsBinTree c e => e -> c -> c -> c
- balanceR :: IsBinTree c e => e -> c -> c -> c
- glue :: IsBinTree c e => c -> c -> c
- merge :: IsBinTree c e => c -> c -> c
- filterGt :: IsBinTree c e => (e -> Ordering) -> c -> MaybeS c
- filterLt :: IsBinTree c e => (e -> Ordering) -> c -> MaybeS c
- insert :: IsBinTree c e => (e -> e -> Ordering) -> e -> c -> Updated c
- delete :: IsBinTree c e => (e -> Ordering) -> c -> MaybeS c
- union :: IsBinTree c e => (e -> e -> Ordering) -> c -> c -> c
- link :: IsBinTree c e => e -> c -> c -> c
- data PairS f s = PairS !f !s

# Documentation

data MaybeS v Source #

A strict version of `Maybe`

Constructors

JustS !v |
NothingS |

#### Instances

Instances details

Alternative MaybeS Source # |
Instance details Defined in Data.Parameterized.Utils.BinTree Methods empty :: MaybeS a Source # (<|>) :: MaybeS a -> MaybeS a -> MaybeS a Source # some :: MaybeS a -> MaybeS [a] Source # many :: MaybeS a -> MaybeS [a] Source #
Applicative MaybeS Source # |
Instance details Defined in Data.Parameterized.Utils.BinTree Methods pure :: a -> MaybeS a Source # (<*>) :: MaybeS (a -> b) -> MaybeS a -> MaybeS b Source # liftA2 :: (a -> b -> c) -> MaybeS a -> MaybeS b -> MaybeS c Source # (*>) :: MaybeS a -> MaybeS b -> MaybeS b Source # (<*) :: MaybeS a -> MaybeS b -> MaybeS a Source #
Functor MaybeS Source # |
Instance details Defined in Data.Parameterized.Utils.BinTree Methods fmap :: (a -> b) -> MaybeS a -> MaybeS b Source # (<$) :: a -> MaybeS b -> MaybeS a Source #

fromMaybeS :: a -> MaybeS a -> a Source #

data Updated a Source #

`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 Source #

data TreeApp e t Source #

Constructors

BinTree !e !t !t |
TipTree |

class IsBinTree t e | t -> e where Source #

Methods

asBin :: t -> TreeApp e t Source #

tip :: t Source #

bin :: e -> t -> t -> t Source #

size :: t -> Int Source #

#### Instances

Instances details

IsBinTree (MapF k2 a) (Pair k2 a) Source # |
Instance details Defined in Data.Parameterized.Map Methods asBin :: MapF k2 a -> TreeApp (Pair k2 a) (MapF k2 a) Source # tip :: MapF k2 a Source # bin :: Pair k2 a -> MapF k2 a -> MapF k2 a -> MapF k2 a Source # size :: MapF k2 a -> Int Source #

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

`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 Source #

`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 Source #

`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 Source #

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

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

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 Source #

`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 Source #

`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 Source #

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 Source #

Union two sets

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

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

data PairS f s Source #

A Strict pair

Constructors

PairS !f !s |