Data.Tree.BST.Intern.Lookup

Implementation of the lookup algorithm over internalist BST trees. Since the lookup does not modify the tree, there is no need for proofs.

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 BST t. The lookup is defined at the value level and the type level. 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 -> BST t -> a

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.Intern.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 -> BST ('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 BST t. 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 -> BST t -> Proxy o -> a