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 l a

a newtype that is labeled with some typelevel tag

Constructors

MkLabeled

Fields

• unLabel :: a

Instances

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)

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

Generic (Labeled l2 a)

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)

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.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

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) '[])

a labeled HNode Leaf

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

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

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

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

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

Generic1 (Proxy :: k -> Type)

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

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

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

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

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

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

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

Defined in Data.Proxy

Methods

mzero :: Proxy a

mplus :: Proxy a -> Proxy a -> Proxy a

Monoid (Proxy s)

Since: base-4.7.0.0

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

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

Defined in Data.Proxy

Methods

minBound :: Proxy t

maxBound :: Proxy t

Enum (Proxy s)

Since: base-4.7.0.0

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)

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

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

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

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

Defined in Data.Proxy

Methods

(==) :: Proxy s -> Proxy s -> Bool

(/=) :: Proxy s -> Proxy s -> Bool

Ord (Proxy s)

Since: base-4.7.0.0

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

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

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

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

Methods

evidence :: forall {proxy}. 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 '[])

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 '[])

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 elem typ t | 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 t where ...

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 ...

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

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