Data.Tree.BST.Extern.Lookup

Implementation of the lookup algorithm over ITree trees for externalist BST trees.

Documentation

class Lookupable (x :: Nat) (a :: Type) (t :: Tree) where

This type class provides the functionality to lookup a node with key x in a non empty tree t without checking any structural invariant (key ordering). The lookup is defined at the value level and the type level, and is performed as if the tree is a BST. It's necessary to know the type a of the value stored in node with key x so that the type of the value returned by lookup may be specified.

Methods

lookup :: (t ~ 'ForkTree l (Node n a1) r, Member x t t ~ 'True) => Proxy x -> ITree t -> a

Lookup the given key in the tree.

Instances

(t ~ 'ForkTree l (Node n a1) r, a ~ LookupValueType x t t, o ~ CmpNat x n, Lookupable' x a ('ForkTree l (Node n a1) r) o) => Lookupable x a ('ForkTree l (Node n a1) r)

Defined in Data.Tree.BST.Extern.Lookup

Methods

lookup :: forall (l0 :: Tree) (n0 :: Nat) a10 (r0 :: Tree). ('ForkTree l (Node n a1) r ~ 'ForkTree l0 (Node n0 a10) r0, Member x ('ForkTree l (Node n a1) r) ('ForkTree l (Node n a1) r) ~ 'True) => Proxy x -> ITree ('ForkTree l (Node n a1) r) -> a

class Lookupable' (x :: Nat) (a :: Type) (t :: Tree) (o :: Ordering) where

This type class provides the functionality to lookup a node with key x in a non empty tree t without checking any structural invariant (key ordering). It's only used by the Lookupable class and it has one extra parameter o, which is the type level comparison of x with the key value of the root node. The o parameter guides the lookup.

Methods

lookup' :: Proxy x -> ITree t -> Proxy o -> a