fcf-containers-0.4.0: Data structures and algorithms for first-class-families

Copyright(c) gspia 2020-
LicenseBSD
Maintainergspia
Safe HaskellSafe
LanguageHaskell2010

Fcf.Data.Tree

Description

Fcf.Data.Tree

Tree provides an interface which is similar to the that given by the container-package. If a method is missing here that you need, please do open up an issue or better, make a PR.

This module provides it's own but (almost) identical definitions of Tree and Forest. The reason for not using the definitions given in the containers is that since nothing else is needed from containers, we are able to have less dependencies.

Many of the examples are from containers-package.

Synopsis

Documentation

>>> import qualified GHC.TypeLits as TL
>>> import           Fcf.Data.Nat

data Tree a Source #

Same as in containers, except not used for any term-level computation in this module.

Constructors

Node a [Tree a] 
Instances
type Eval (FoldTree f (Node a3 (x ': xs)) :: a2 -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (FoldTree f (Node a3 (x ': xs)) :: a2 -> Type) = Eval (f a3 (Eval (Map (FoldTree f) (x ': xs))))
type Eval (FoldTree f (Node a3 ([] :: [Tree a1])) :: a2 -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (FoldTree f (Node a3 ([] :: [Tree a1])) :: a2 -> Type) = Eval (f a3 ([] :: [a2]))
type Eval (GetForest (Node _ f) :: [Tree a] -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (GetForest (Node _ f) :: [Tree a] -> Type) = f
type Eval (GetForests ts :: [Tree a] -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (GetForests ts :: [Tree a] -> Type) = Eval (ConcatMap (GetForest :: Tree a -> [Tree a] -> Type) ts)
type Eval (SubFLevels (t ': ts) :: Maybe ([a], [Tree a]) -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (SubFLevels (t ': ts) :: Maybe ([a], [Tree a]) -> Type) = Just ((,) (Eval (GetRoots (t ': ts))) (Eval (GetForests (t ': ts))))
type Eval (SubFLevels ([] :: [Tree a]) :: Maybe ([a], [Tree a]) -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (SubFLevels ([] :: [Tree a]) :: Maybe ([a], [Tree a]) -> Type) = (Nothing :: Maybe ([a], [Tree a]))
type Eval (TreeToFix (Node a2 (b ': bs)) :: Fix (TreeF a1) -> Type) Source # 
Instance details

Defined in Fcf.Alg.Tree

type Eval (TreeToFix (Node a2 (b ': bs)) :: Fix (TreeF a1) -> Type) = Fix (NodeF a2 (Eval (Map (TreeToFix :: Tree a1 -> Fix (TreeF a1) -> Type) (b ': bs))))
type Eval (TreeToFix (Node a2 ([] :: [Tree a1])) :: Fix (TreeF a1) -> Type) Source # 
Instance details

Defined in Fcf.Alg.Tree

type Eval (TreeToFix (Node a2 ([] :: [Tree a1])) :: Fix (TreeF a1) -> Type) = Fix (NodeF a2 ([] :: [Fix (TreeF a1)]))
type Eval (UnfoldForest f bs :: Forest a1 -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (UnfoldForest f bs :: Forest a1 -> Type) = Eval (Map (UnfoldTree f) bs)
type Eval (UnfoldTree f b2 :: Tree a -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (UnfoldTree f b2 :: Tree a -> Type) = Node (Eval ((Fst :: (a, [b1]) -> a -> Type) =<< f b2)) (Eval (UnfoldForest f (Eval ((Snd :: (a, [b1]) -> [b1] -> Type) =<< f b2))))

type Forest a = [Tree a] Source #

Same as in containers, except not used for any term-level computation in this module.

data FoldTree :: (a -> [b] -> Exp b) -> Tree a -> Exp b Source #

Fold a type-level Tree.

Instances
type Eval (FoldTree f (Node a3 (x ': xs)) :: a2 -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (FoldTree f (Node a3 (x ': xs)) :: a2 -> Type) = Eval (f a3 (Eval (Map (FoldTree f) (x ': xs))))
type Eval (FoldTree f (Node a3 ([] :: [Tree a1])) :: a2 -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (FoldTree f (Node a3 ([] :: [Tree a1])) :: a2 -> Type) = Eval (f a3 ([] :: [a2]))

data UnfoldTree :: (b -> Exp (a, [b])) -> b -> Exp (Tree a) Source #

Unfold for a Tree.

Example

Expand
>>> data BuildNode :: Nat -> Exp (Nat,[Nat])
>>> :{
  type instance Eval (BuildNode x) =
      If (Eval ((2 TL.* x TL.+ 1) >= 8))
          '(x, '[])
          '(x, '[2 TL.* x, (2 TL.* x) TL.+ 1 ])
:}
>>> :kind! Eval (UnfoldTree BuildNode 1)
Eval (UnfoldTree BuildNode 1) :: Tree Nat
= 'Node
    1
    '[ 'Node 2 '[ 'Node 4 '[], 'Node 5 '[]],
       'Node 3 '[ 'Node 6 '[], 'Node 7 '[]]]
Instances
type Eval (UnfoldTree f b2 :: Tree a -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (UnfoldTree f b2 :: Tree a -> Type) = Node (Eval ((Fst :: (a, [b1]) -> a -> Type) =<< f b2)) (Eval (UnfoldForest f (Eval ((Snd :: (a, [b1]) -> [b1] -> Type) =<< f b2))))

data UnfoldForest :: (b -> Exp (a, [b])) -> [b] -> Exp (Forest a) Source #

Unfold for a Forest.

Instances
type Eval (UnfoldForest f bs :: Forest a1 -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (UnfoldForest f bs :: Forest a1 -> Type) = Eval (Map (UnfoldTree f) bs)

data Flatten :: Tree a -> Exp [a] Source #

Flatten a Tree.

Example

Expand
>>> :kind! Eval (Flatten ('Node 1 '[ 'Node 2 '[ 'Node 3 '[ 'Node 4 '[]]], 'Node 5 '[ 'Node 6 '[]]]))
Eval (Flatten ('Node 1 '[ 'Node 2 '[ 'Node 3 '[ 'Node 4 '[]]], 'Node 5 '[ 'Node 6 '[]]])) :: [Nat]
= '[1, 2, 3, 4, 5, 6]
Instances
type Eval (Flatten (Node a fs) :: [b] -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (Flatten (Node a fs) :: [b] -> Type) = a ': Eval (ConcatMap (Flatten :: Tree b -> [b] -> Type) fs)

data GetRoot :: Tree a -> Exp a Source #

Get the root node from a Tree.

Instances
type Eval (GetRoot (Node a2 _) :: a1 -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (GetRoot (Node a2 _) :: a1 -> Type) = a2

data GetForest :: Tree a -> Exp [Tree a] Source #

Get the forest from a Tree.

Instances
type Eval (GetForest (Node _ f) :: [Tree a] -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (GetForest (Node _ f) :: [Tree a] -> Type) = f

data GetRoots :: [Tree a] -> Exp [a] Source #

Get the root nodes from a list of Trees.

Instances
type Eval (GetRoots trs :: [b] -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (GetRoots trs :: [b] -> Type) = Eval (Map (GetRoot :: Tree b -> b -> Type) trs)

data GetForests :: [Tree a] -> Exp [Tree a] Source #

Get the forests from a list of Trees.

Instances
type Eval (GetForests ts :: [Tree a] -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (GetForests ts :: [Tree a] -> Type) = Eval (ConcatMap (GetForest :: Tree a -> [Tree a] -> Type) ts)

data SubFLevels :: [Tree a] -> Exp (Maybe ([a], [Tree a])) Source #

Instances
type Eval (SubFLevels (t ': ts) :: Maybe ([a], [Tree a]) -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (SubFLevels (t ': ts) :: Maybe ([a], [Tree a]) -> Type) = Just ((,) (Eval (GetRoots (t ': ts))) (Eval (GetForests (t ': ts))))
type Eval (SubFLevels ([] :: [Tree a]) :: Maybe ([a], [Tree a]) -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (SubFLevels ([] :: [Tree a]) :: Maybe ([a], [Tree a]) -> Type) = (Nothing :: Maybe ([a], [Tree a]))

data Levels :: Tree a -> Exp [[a]] Source #

Get the levels from a Tree.

Example

Expand
>>> :kind! Eval (Levels ('Node 1 '[ 'Node 2 '[ 'Node 3 '[ 'Node 4 '[]]], 'Node 5 '[ 'Node 6 '[]]]))
Eval (Levels ('Node 1 '[ 'Node 2 '[ 'Node 3 '[ 'Node 4 '[]]], 'Node 5 '[ 'Node 6 '[]]])) :: [[Nat]]
= '[ '[1], '[2, 5], '[3, 6], '[4]]
Instances
type Eval (Levels tr :: [[a]] -> Type) Source # 
Instance details

Defined in Fcf.Data.Tree

type Eval (Levels tr :: [[a]] -> Type) = Eval (Unfoldr (SubFLevels :: [Tree a] -> Maybe ([a], [Tree a]) -> Type) (tr ': ([] :: [Tree a])))