Type.Set

Core type

data TypeSet a

A binary search tree. When -XDataKinds is turned on, this becomes the backbone of the type-level set.

>>> type MySet = Insert Bool (Insert String (Insert (Maybe Int) 'Empty))

Constructors

Empty

Branch a (TypeSet a) (TypeSet a)

Set operations

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

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

Equations

Member t Empty = False

Member t (Branch a lbst rbst) = MemberImpl (CmpType t a) t lbst rbst

type family Insert (t :: k) (bst :: TypeSet k) :: TypeSet k where ...

O(log n). Insert an element into the TypeSet.

Equations

Insert t Empty = Branch t Empty Empty

Insert t (Branch a lbst rbst) = InsertImpl (CmpType t a) t a lbst rbst

type family Remove (t :: k) (bst :: TypeSet k) :: TypeSet k where ...

O(log n). Remove an element from the TypeSet.

Equations

Remove t Empty = Empty

Remove t (Branch a lbst rbst) = RemoveImpl (CmpType t a) t a lbst rbst

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 (Branch a lbst rbst) big = Merge rbst (Merge lbst (Insert a big))

Tree operations

type family Locate (t :: k) (bst :: TypeSet k) :: [Side] where ...

O(log n). Compute a [Side] which finds the desired element in the tree. The result of this can be passed to Follow in order to look up the same element again later.

Equations

Member t (Branch a lbst rbst) = LocateImpl (CmpType t a) t lbst rbst

Member t Empty = TypeError (Text "Unable to locate: " :<>: ShowType t)

type family Follow (ss :: [Side]) (bst :: TypeSet k) :: k where ...

O(log n). Follow the result of a Locate to get a particular element in the tree.

Equations

Follow '[] (Branch t _ _) = t

Follow (L ': ss) (Branch _ l _) = Follow ss l

Follow (R ': ss) (Branch _ _ r) = Follow ss r

Follow ss Empty = TypeError (Text "Unable to follow: " :<>: ShowType ss)

data Side

Either left or right down a path.

Constructors

L

R

Instances

Eq Side

Defined in Type.Set

Methods

(==) :: Side -> Side -> Bool

(/=) :: Side -> Side -> Bool

Ord Side

Defined in Type.Set

Methods

compare :: Side -> Side -> Ordering

(<) :: Side -> Side -> Bool

(<=) :: Side -> Side -> Bool

(>) :: Side -> Side -> Bool

(>=) :: Side -> Side -> Bool

max :: Side -> Side -> Side

min :: Side -> Side -> Side

Show Side

Defined in Type.Set

Methods

showsPrec :: Int -> Side -> ShowS

show :: Side -> String

showList :: [Side] -> ShowS

FromSides ([] :: [Side])

Defined in Type.Set.Variant

Methods

fromSides :: SSide []

TestEquality SSide

Defined in Type.Set.Variant

Methods

testEquality :: SSide a -> SSide b -> Maybe (a :~: b)

FromSides ss => FromSides (L ': ss)

Defined in Type.Set.Variant

Methods

fromSides :: SSide (L ': ss)

FromSides ss => FromSides (R ': ss)

Defined in Type.Set.Variant

Methods

fromSides :: SSide (R ': ss)