Data.HTree.Labeled

This module implements a search in a typelevel tree and offers a handy interface via -XOverloaedRecordDot and HasField. We can search in the tree via BFS or DFS. Performance wise this doesn't make a difference, as the search is performed at compile time anyway however, it can change the semantics if the tree contains an element more than once, see the example in getElem.

Interface

Labeled types

newtype Labeled (l1 :: l) a

a newtype that is labeled with some typelevel tag

Constructors

MkLabeled

Fields

• unLabel :: a

Instances

Functor (Labeled l2)

Defined in Data.HTree.Labeled

Methods

fmap :: (a -> b) -> Labeled l2 a -> Labeled l2 b

(<$) :: a -> Labeled l2 b -> Labeled l2 a

Foldable (Labeled l2)

Defined in Data.HTree.Labeled

Methods

fold :: Monoid m => Labeled l2 m -> m

foldMap :: Monoid m => (a -> m) -> Labeled l2 a -> m

foldMap' :: Monoid m => (a -> m) -> Labeled l2 a -> m

foldr :: (a -> b -> b) -> b -> Labeled l2 a -> b

foldr' :: (a -> b -> b) -> b -> Labeled l2 a -> b

foldl :: (b -> a -> b) -> b -> Labeled l2 a -> b

foldl' :: (b -> a -> b) -> b -> Labeled l2 a -> b

foldr1 :: (a -> a -> a) -> Labeled l2 a -> a

foldl1 :: (a -> a -> a) -> Labeled l2 a -> a

toList :: Labeled l2 a -> [a]

null :: Labeled l2 a -> Bool

length :: Labeled l2 a -> Int

elem :: Eq a => a -> Labeled l2 a -> Bool

maximum :: Ord a => Labeled l2 a -> a

minimum :: Ord a => Labeled l2 a -> a

sum :: Num a => Labeled l2 a -> a

product :: Num a => Labeled l2 a -> a

Traversable (Labeled l2)

Defined in Data.HTree.Labeled

Methods

traverse :: Applicative f => (a -> f b) -> Labeled l2 a -> f (Labeled l2 b)

sequenceA :: Applicative f => Labeled l2 (f a) -> f (Labeled l2 a)

mapM :: Monad m => (a -> m b) -> Labeled l2 a -> m (Labeled l2 b)

sequence :: Monad m => Labeled l2 (m a) -> m (Labeled l2 a)

Generic (Labeled l2 a)

Defined in Data.HTree.Labeled

Associated Types

type Rep (Labeled l2 a)

Defined in Data.HTree.Labeled

type Rep (Labeled l2 a) = D1 ('MetaData "Labeled" "Data.HTree.Labeled" "htree-0.2.0.0-inplace" 'True) (C1 ('MetaCons "MkLabeled" 'PrefixI 'True) (S1 ('MetaSel ('Just "unLabel") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)))

Methods

from :: Labeled l2 a -> Rep (Labeled l2 a) x

to :: Rep (Labeled l2 a) x -> Labeled l2 a

Show a => Show (Labeled l2 a)

Defined in Data.HTree.Labeled

Methods

showsPrec :: Int -> Labeled l2 a -> ShowS

show :: Labeled l2 a -> String

showList :: [Labeled l2 a] -> ShowS

Eq a => Eq (Labeled l2 a)

Defined in Data.HTree.Labeled

Methods

(==) :: Labeled l2 a -> Labeled l2 a -> Bool

(/=) :: Labeled l2 a -> Labeled l2 a -> Bool

Ord a => Ord (Labeled l2 a)

Defined in Data.HTree.Labeled

Methods

compare :: Labeled l2 a -> Labeled l2 a -> Ordering

(<) :: Labeled l2 a -> Labeled l2 a -> Bool

(<=) :: Labeled l2 a -> Labeled l2 a -> Bool

(>) :: Labeled l2 a -> Labeled l2 a -> Bool

(>=) :: Labeled l2 a -> Labeled l2 a -> Bool

max :: Labeled l2 a -> Labeled l2 a -> Labeled l2 a

min :: Labeled l2 a -> Labeled l2 a -> Labeled l2 a

type Rep (Labeled l2 a)

Defined in Data.HTree.Labeled

type Rep (Labeled l2 a) = D1 ('MetaData "Labeled" "Data.HTree.Labeled" "htree-0.2.0.0-inplace" 'True) (C1 ('MetaCons "MkLabeled" 'PrefixI 'True) (S1 ('MetaSel ('Just "unLabel") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)))

pattern HNodeL :: forall {l1} (l2 :: l1) a f (ts :: TyForest Type). Functor f => f a -> HForest f ts -> HTree f ('TyNode (Labeled l2 a) ts) infixr 4

a pattern that allows for direct construction and destruction of nodes with labels

pattern HLeafL :: forall {l1} (l2 :: l1) a f. Functor f => f a -> HTree f ('TyNode (Labeled l2 a) ('[] :: [TyTree Type]))

a labeled HNode Leaf

type TyNodeL (l1 :: l) a = 'TyNode (Labeled l1 a) infixr 4

a type syonym that allows for easy construction of TyTrees that have labeled nodes

Getting elements

getElem :: forall {k} (t :: TyTree Type) f. forall (strat :: SearchStrategy) (l :: k) typ -> (HasField' strat (Labeled l typ) t, Functor f) => HTree f t -> f typ

searches a tree for an element and returns that element, specialised to Labeled and unwraps

>>> import Data.Functor.Identity
>>> type T = TyNodeL "top" Int [ TyNodeL "inter" Int '[ TyNodeL "foo" Int '[]], TyNodeL "foo" Int '[]]
>>> t :: HTree Identity T = 42 `HNodeL` HNodeL 4 (HNodeL 69 HNil `HCons` HNil) `HCons` HNodeL 67 HNil `HCons` HNil
>>> getElem DFS "foo" Int t
Identity 69
>>> getElem BFS "foo" Int t
Identity 67

getElem' :: forall (t :: TyTree Type) f. forall (strat :: SearchStrategy) typ -> HasField' strat typ t => HTree f t -> f typ

searches a tree for an element and returns that element

data SearchStrategy

the search strategy used in HasField', this is intended to be used only as a DataKind

Constructors

DFS

BFS

Reexports

class HasField (x :: k) r a | x r -> a where

Constraint representing the fact that the field x belongs to the record type r and has field type a. This will be solved automatically, but manual instances may be provided as well.

Methods

getField :: r -> a

Selector function to extract the field from the record.

Instances

(HasField' 'BFS (Labeled l typ) t, Functor f) => HasField (l :: k) (HTree f t) (f typ)

Defined in Data.HTree.Labeled

Methods

getField :: HTree f t -> f typ

Internal

class HasField' (strat :: SearchStrategy) typ (t :: TyTree Type) | strat t -> typ where

This is the helper class that creates evidence, it implements a DFS together with Decide

Methods

evidence :: proxy strat -> Path typ t

Instances

HasField' 'BFS typ ('TyNode typ (t ': ts))

Defined in Data.HTree.Labeled

Methods

evidence :: proxy 'BFS -> Path typ ('TyNode typ (t ': ts))

HasField' 'BFS typ ('TyNode typ ('[] :: [TyTree Type]))

Defined in Data.HTree.Labeled

Methods

evidence :: proxy 'BFS -> Path typ ('TyNode typ ('[] :: [TyTree Type]))

Decide 'BFS (AnyElem typ ts) typ ('TyNode typ' (t ': ts)) => HasField' 'BFS typ ('TyNode typ' (t ': ts))

Defined in Data.HTree.Labeled

Methods

evidence :: proxy 'BFS -> Path typ ('TyNode typ' (t ': ts))

HasField' 'DFS typ ('TyNode typ (t ': ts))

Defined in Data.HTree.Labeled

Methods

evidence :: proxy 'DFS -> Path typ ('TyNode typ (t ': ts))

HasField' 'DFS typ ('TyNode typ ('[] :: [TyTree Type]))

Defined in Data.HTree.Labeled

Methods

evidence :: proxy 'DFS -> Path typ ('TyNode typ ('[] :: [TyTree Type]))

Decide 'DFS (Not (Elem typ t)) typ ('TyNode typ' (t ': ts)) => HasField' 'DFS typ ('TyNode typ' (t ': ts))

Defined in Data.HTree.Labeled

Methods

evidence :: proxy 'DFS -> Path typ ('TyNode typ' (t ': ts))

class Decide (strat :: SearchStrategy) (elem :: Bool) typ (t :: TyTree Type) | strat t -> typ where

Together with HasField' implements a DFS in the tree

Methods

evidence' :: forall {proxy :: forall k. k -> Type}. proxy strat -> proxy elem -> Path typ t

Instances

HasField' strat typ t => Decide strat 'False typ ('TyNode typ' (t ': ts'))

Defined in Data.HTree.Labeled

Methods

evidence' :: forall {proxy :: forall k. k -> Type}. proxy strat -> proxy 'False -> Path typ ('TyNode typ' (t ': ts'))

HasField' strat typ ('TyNode typ' ts) => Decide strat 'True typ ('TyNode typ' (t' ': ts))

Defined in Data.HTree.Labeled

Methods

evidence' :: forall {proxy :: forall k. k -> Type}. proxy strat -> proxy 'True -> Path typ ('TyNode typ' (t' ': ts))

type family Elem (typ :: k) (t :: TyTree k) :: Bool where ...

simple typelevel predicate that tests whether some element is in a tree

Equations

Elem (a2 :: a1) ('TyNode a2 ts :: TyTree a1) = 'True

Elem (a :: k) ('TyNode a' ts :: TyTree k) = AnyElem a ts

Elem (a :: k) (t :: TyTree k) = 'False

type family AnyElem (typ :: k) (ts :: TyForest k) :: Bool where ...

typelevel predicate that tests whether the element is in any of the subtrees

Equations

AnyElem (a :: k) (t ': ts :: [TyTree k]) = Elem a t || AnyElem a ts

AnyElem (a :: k) ('[] :: [TyTree k]) = 'False

getElemWithPath :: forall {k} (typ :: k) (t :: TyTree k) f. Path typ t -> HTree f t -> f typ

gets an element given a path into the tree

Orphan instances

(HasField' 'BFS (Labeled l typ) t, Functor f) => HasField (l :: k) (HTree f t) (f typ)

Methods

getField :: HTree f t -> f typ