Type.RBSet

See here for the original term-level code by Stefan Kahrs.

Since: 0.1.1.0

Core type

data TypeSet a

A Red-Black tree.

Since: 0.1.1.0

Constructors

E

N Color (TypeSet a) a (TypeSet a)

Instances

Eq a => Eq (TypeSet a)

Defined in Type.RBSet

Methods

(==) :: TypeSet a -> TypeSet a -> Bool

(/=) :: TypeSet a -> TypeSet a -> Bool

Show a => Show (TypeSet a)

Defined in Type.RBSet

Methods

showsPrec :: Int -> TypeSet a -> ShowS

show :: TypeSet a -> String

showList :: [TypeSet a] -> ShowS

type Empty = E

A map without entries.

Set operations

type family Member (t :: k) (bst :: TypeSet k) :: Bool where ...

O(log n). Determine membership in the 'TypeSet.'

Equations

Member t E = False

Member t (N _ lbst a rbst) = MemberImpl (CmpType t a) t lbst rbst

class Insertable (k :: ki) (t :: TypeSet ki)

The associated type family Insert produces the resulting map.

Associated Types

type Insert k t :: TypeSet ki

Instances

(InsertableHelper1 k t, Insert1 k t ~ inserted, CanMakeBlack inserted) => Insertable (k :: ki) (t :: TypeSet ki)

Defined in Type.RBSet

Associated Types

type Insert k t :: TypeSet ki

type family InsertAll (es :: [k]) (t :: TypeSet k) :: TypeSet k where ...

Insert a list of type level key / value pairs into a type-level map.

Equations

InsertAll '[] t = t

InsertAll (v ': es) t = Insert v (InsertAll es t)

type FromList (es :: [k]) = InsertAll es Empty

Build a type-level map out of a list of type level key / value pairs.

class Removable (k :: ki) (t :: TypeSet ki)

The associated type family Remove produces the resulting map.

Associated Types

type Remove k t :: TypeSet ki

Instances

(Delable k t, Del k t ~ deleted, CanMakeBlack deleted) => Removable (k :: ki) (t :: TypeSet ki)

Defined in Type.RBSet

Associated Types

type Remove k t :: TypeSet ki

type family Merge (small :: TypeSet k) (big :: TypeSet k) :: TypeSet k where ...

O(m log n) for Merge m n; put your smaller set on the left side. Merge two TypeSets together.

Equations

Merge Empty big = big

Merge small Empty = small

Merge (N _ lbst a rbst) big = Merge rbst (Merge lbst (Insert a big))