Safe Haskell	Safe-Inferred
Language	GHC2021

Data.HTree.Labeled

Contents

Interface
Internal
Orphan instances

Description

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.

Synopsis

newtype Labeled l a = MkLabeled {
- unLabel :: a
}
pattern HNodeL :: forall l a f ts. Functor f => f a -> HForest f ts -> HTree f ('TyNode (Labeled l a) ts)
pattern HLeafL :: forall l a f. Functor f => f a -> HTree f ('TyNode (Labeled l a) '[])
type TyNodeL l a = 'TyNode (Labeled l a)
getElem :: forall {proxy} strat l typ t f. (HasField' (strat :: SearchStrategy) (Labeled l typ) t, Functor f) => proxy strat -> HTree f t -> f typ
getElem' :: forall {proxy} strat typ t f. HasField' (strat :: SearchStrategy) typ t => proxy strat -> HTree f t -> f typ
data SearchStrategy
- = DFS
- | BFS
class HasField (x :: k) r a | x r -> a where
- getField :: r -> a
data Proxy (t :: k) = Proxy
class HasField' strat typ t | strat t -> typ where
- evidence :: forall {proxy}. proxy strat -> Path typ t
class Decide strat elem typ t | strat t -> typ where
- evidence' :: forall {proxy :: forall k. k -> Type}. proxy strat -> proxy elem -> Path typ t
type family Elem typ t where ...
type family AnyElem typ ts where ...
getElemWithPath :: forall typ t f. Path typ t -> HTree f t -> f typ

Interface

Labeled types

newtype Labeled l a Source #

a newtype that is labeled with some typelevel tag

Constructors

MkLabeled
Fields unLabel :: a

Instances

Instances details

Foldable (Labeled l2) Source #
Instance details 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) Source #
Instance details 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) #
Functor (Labeled l2) Source #
Instance details Defined in Data.HTree.Labeled Methods fmap :: (a -> b) -> Labeled l2 a -> Labeled l2 b # (<$) :: a -> Labeled l2 b -> Labeled l2 a #
Generic (Labeled l2 a) Source #
Instance details Defined in Data.HTree.Labeled Associated Types type Rep (Labeled l2 a) :: Type -> Type # 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) Source #
Instance details 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) Source #
Instance details 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) Source #
Instance details 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) Source #
Instance details Defined in Data.HTree.Labeled type Rep (Labeled l2 a) = D1 ('MetaData "Labeled" "Data.HTree.Labeled" "htree-0.1.1.0-inplace" 'True) (C1 ('MetaCons "MkLabeled" 'PrefixI 'True) (S1 ('MetaSel ('Just "unLabel") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)))

pattern HNodeL :: forall l a f ts. Functor f => f a -> HForest f ts -> HTree f ('TyNode (Labeled l a) ts) infixr 4 Source #

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

pattern HLeafL :: forall l a f. Functor f => f a -> HTree f ('TyNode (Labeled l a) '[]) Source #

a labeled HNode Leaf

type TyNodeL l a = 'TyNode (Labeled l a) infixr 4 Source #

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

Getting elements

getElem :: forall {proxy} strat l typ t f. (HasField' (strat :: SearchStrategy) (Labeled l typ) t, Functor f) => proxy strat -> HTree f t -> f typ Source #

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 Proxy t
Identity 69
>>> getElem @'BFS @"foo" @Int Proxy t
Identity 67

getElem' :: forall {proxy} strat typ t f. HasField' (strat :: SearchStrategy) typ t => proxy strat -> HTree f t -> f typ Source #

searches a tree for an element and returns that element

data SearchStrategy Source #

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

Instances details

(HasField' 'BFS (Labeled l typ) t, Functor f) => HasField (l :: k) (HTree f t) (f typ) Source #
Instance details Defined in Data.HTree.Labeled Methods getField :: HTree f t -> f typ #

data Proxy (t :: k) #

Proxy is a type that holds no data, but has a phantom parameter of arbitrary type (or even kind). Its use is to provide type information, even though there is no value available of that type (or it may be too costly to create one).

Historically, Proxy :: Proxy a is a safer alternative to the undefined :: a idiom.

>>> Proxy :: Proxy (Void, Int -> Int)
Proxy

Proxy can even hold types of higher kinds,

>>> Proxy :: Proxy Either
Proxy

>>> Proxy :: Proxy Functor
Proxy

>>> Proxy :: Proxy complicatedStructure
Proxy

Constructors

Proxy

Instances

Instances details

Generic1 (Proxy :: k -> Type)
Instance details Defined in GHC.Generics Associated Types type Rep1 Proxy :: k -> Type # Methods from1 :: forall (a :: k0). Proxy a -> Rep1 Proxy a # to1 :: forall (a :: k0). Rep1 Proxy a -> Proxy a #
Foldable (Proxy :: Type -> Type)	Since: base-4.7.0.0
Instance details Defined in Data.Foldable Methods fold :: Monoid m => Proxy m -> m # foldMap :: Monoid m => (a -> m) -> Proxy a -> m # foldMap' :: Monoid m => (a -> m) -> Proxy a -> m # foldr :: (a -> b -> b) -> b -> Proxy a -> b # foldr' :: (a -> b -> b) -> b -> Proxy a -> b # foldl :: (b -> a -> b) -> b -> Proxy a -> b # foldl' :: (b -> a -> b) -> b -> Proxy a -> b # foldr1 :: (a -> a -> a) -> Proxy a -> a # foldl1 :: (a -> a -> a) -> Proxy a -> a # toList :: Proxy a -> [a] # null :: Proxy a -> Bool # length :: Proxy a -> Int # elem :: Eq a => a -> Proxy a -> Bool # maximum :: Ord a => Proxy a -> a # minimum :: Ord a => Proxy a -> a # sum :: Num a => Proxy a -> a # product :: Num a => Proxy a -> a #
Traversable (Proxy :: Type -> Type)	Since: base-4.7.0.0
Instance details Defined in Data.Traversable Methods traverse :: Applicative f => (a -> f b) -> Proxy a -> f (Proxy b) # sequenceA :: Applicative f => Proxy (f a) -> f (Proxy a) # mapM :: Monad m => (a -> m b) -> Proxy a -> m (Proxy b) # sequence :: Monad m => Proxy (m a) -> m (Proxy a) #
Alternative (Proxy :: Type -> Type)	Since: base-4.9.0.0
Instance details Defined in Data.Proxy Methods empty :: Proxy a # (<\|>) :: Proxy a -> Proxy a -> Proxy a # some :: Proxy a -> Proxy [a] # many :: Proxy a -> Proxy [a] #
Applicative (Proxy :: Type -> Type)	Since: base-4.7.0.0
Instance details Defined in Data.Proxy Methods pure :: a -> Proxy a # (<>) :: Proxy (a -> b) -> Proxy a -> Proxy b # liftA2 :: (a -> b -> c) -> Proxy a -> Proxy b -> Proxy c # (>) :: Proxy a -> Proxy b -> Proxy b # (<*) :: Proxy a -> Proxy b -> Proxy a #
Functor (Proxy :: Type -> Type)	Since: base-4.7.0.0
Instance details Defined in Data.Proxy Methods fmap :: (a -> b) -> Proxy a -> Proxy b # (<$) :: a -> Proxy b -> Proxy a #
Monad (Proxy :: Type -> Type)	Since: base-4.7.0.0
Instance details Defined in Data.Proxy Methods (>>=) :: Proxy a -> (a -> Proxy b) -> Proxy b # (>>) :: Proxy a -> Proxy b -> Proxy b # return :: a -> Proxy a #
MonadPlus (Proxy :: Type -> Type)	Since: base-4.9.0.0
Instance details Defined in Data.Proxy Methods mzero :: Proxy a # mplus :: Proxy a -> Proxy a -> Proxy a #
Monoid (Proxy s)	Since: base-4.7.0.0
Instance details Defined in Data.Proxy Methods mempty :: Proxy s # mappend :: Proxy s -> Proxy s -> Proxy s # mconcat :: [Proxy s] -> Proxy s #
Semigroup (Proxy s)	Since: base-4.9.0.0
Instance details Defined in Data.Proxy Methods (<>) :: Proxy s -> Proxy s -> Proxy s # sconcat :: NonEmpty (Proxy s) -> Proxy s # stimes :: Integral b => b -> Proxy s -> Proxy s #
Bounded (Proxy t)	Since: base-4.7.0.0
Instance details Defined in Data.Proxy Methods minBound :: Proxy t # maxBound :: Proxy t #
Enum (Proxy s)	Since: base-4.7.0.0
Instance details Defined in Data.Proxy Methods succ :: Proxy s -> Proxy s # pred :: Proxy s -> Proxy s # toEnum :: Int -> Proxy s # fromEnum :: Proxy s -> Int # enumFrom :: Proxy s -> [Proxy s] # enumFromThen :: Proxy s -> Proxy s -> [Proxy s] # enumFromTo :: Proxy s -> Proxy s -> [Proxy s] # enumFromThenTo :: Proxy s -> Proxy s -> Proxy s -> [Proxy s] #
Generic (Proxy t)
Instance details Defined in GHC.Generics Associated Types type Rep (Proxy t) :: Type -> Type # Methods from :: Proxy t -> Rep (Proxy t) x # to :: Rep (Proxy t) x -> Proxy t #
Ix (Proxy s)	Since: base-4.7.0.0
Instance details Defined in Data.Proxy Methods range :: (Proxy s, Proxy s) -> [Proxy s] # index :: (Proxy s, Proxy s) -> Proxy s -> Int # unsafeIndex :: (Proxy s, Proxy s) -> Proxy s -> Int # inRange :: (Proxy s, Proxy s) -> Proxy s -> Bool # rangeSize :: (Proxy s, Proxy s) -> Int # unsafeRangeSize :: (Proxy s, Proxy s) -> Int #
Read (Proxy t)	Since: base-4.7.0.0
Instance details Defined in Data.Proxy Methods readsPrec :: Int -> ReadS (Proxy t) # readList :: ReadS [Proxy t] # readPrec :: ReadPrec (Proxy t) # readListPrec :: ReadPrec [Proxy t] #
Show (Proxy s)	Since: base-4.7.0.0
Instance details Defined in Data.Proxy Methods showsPrec :: Int -> Proxy s -> ShowS # show :: Proxy s -> String # showList :: [Proxy s] -> ShowS #
Eq (Proxy s)	Since: base-4.7.0.0
Instance details Defined in Data.Proxy Methods (==) :: Proxy s -> Proxy s -> Bool # (/=) :: Proxy s -> Proxy s -> Bool #
Ord (Proxy s)	Since: base-4.7.0.0
Instance details Defined in Data.Proxy Methods compare :: Proxy s -> Proxy s -> Ordering # (<) :: Proxy s -> Proxy s -> Bool # (<=) :: Proxy s -> Proxy s -> Bool # (>) :: Proxy s -> Proxy s -> Bool # (>=) :: Proxy s -> Proxy s -> Bool # max :: Proxy s -> Proxy s -> Proxy s # min :: Proxy s -> Proxy s -> Proxy s #
type Rep1 (Proxy :: k -> Type)	Since: base-4.6.0.0
Instance details Defined in GHC.Generics type Rep1 (Proxy :: k -> Type) = D1 ('MetaData "Proxy" "Data.Proxy" "base" 'False) (C1 ('MetaCons "Proxy" 'PrefixI 'False) (U1 :: k -> Type))
type Rep (Proxy t)	Since: base-4.6.0.0
Instance details Defined in GHC.Generics type Rep (Proxy t) = D1 ('MetaData "Proxy" "Data.Proxy" "base" 'False) (C1 ('MetaCons "Proxy" 'PrefixI 'False) (U1 :: Type -> Type))

Internal

class HasField' strat typ t | strat t -> typ where Source #

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

Methods

evidence :: forall {proxy}. proxy strat -> Path typ t Source #

Instances

Instances details

HasField' 'BFS typ ('TyNode typ (t ': ts)) Source #
Instance details Defined in Data.HTree.Labeled Methods evidence :: proxy 'BFS -> Path typ ('TyNode typ (t ': ts)) Source #
HasField' 'BFS typ ('TyNode typ ('[] :: [TyTree Type])) Source #
Instance details Defined in Data.HTree.Labeled Methods evidence :: proxy 'BFS -> Path typ ('TyNode typ '[]) Source #
Decide 'BFS (AnyElem typ ts) typ ('TyNode typ' (t ': ts)) => HasField' 'BFS typ ('TyNode typ' (t ': ts)) Source #
Instance details Defined in Data.HTree.Labeled Methods evidence :: proxy 'BFS -> Path typ ('TyNode typ' (t ': ts)) Source #
HasField' 'DFS typ ('TyNode typ (t ': ts)) Source #
Instance details Defined in Data.HTree.Labeled Methods evidence :: proxy 'DFS -> Path typ ('TyNode typ (t ': ts)) Source #
HasField' 'DFS typ ('TyNode typ ('[] :: [TyTree Type])) Source #
Instance details Defined in Data.HTree.Labeled Methods evidence :: proxy 'DFS -> Path typ ('TyNode typ '[]) Source #
Decide 'DFS (Not (Elem typ t)) typ ('TyNode typ' (t ': ts)) => HasField' 'DFS typ ('TyNode typ' (t ': ts)) Source #
Instance details Defined in Data.HTree.Labeled Methods evidence :: proxy 'DFS -> Path typ ('TyNode typ' (t ': ts)) Source #

class Decide strat elem typ t | strat t -> typ where Source #

Together with HasField' implements a DFS in the tree

Methods

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

Instances

Instances details

HasField' strat typ t => Decide strat 'False typ ('TyNode typ' (t ': ts')) Source #
Instance details Defined in Data.HTree.Labeled Methods evidence' :: forall {proxy :: forall k. k -> Type}. proxy strat -> proxy 'False -> Path typ ('TyNode typ' (t ': ts')) Source #
HasField' strat typ ('TyNode typ' ts) => Decide strat 'True typ ('TyNode typ' (t' ': ts)) Source #
Instance details Defined in Data.HTree.Labeled Methods evidence' :: forall {proxy :: forall k. k -> Type}. proxy strat -> proxy 'True -> Path typ ('TyNode typ' (t' ': ts)) Source #

type family Elem typ t where ... Source #

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

Equations

Elem a ('TyNode a ts) = 'True
Elem a ('TyNode a' ts) = AnyElem a ts
Elem a t = 'False

type family AnyElem typ ts where ... Source #

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

Equations

AnyElem a (t : ts) = Elem a t \|\| AnyElem a ts
AnyElem a '[] = 'False

getElemWithPath :: forall typ t f. Path typ t -> HTree f t -> f typ Source #

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) Source #
Instance details Methods getField :: HTree f t -> f typ #