Fcf.Data.Tree

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.

Documentation

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

data Tree a

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)

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)

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)

Defined in Fcf.Data.Tree

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

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

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)

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)

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)

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)

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)

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)

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]

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

Fold a type-level Tree.

Instances

type Eval (FoldTree f (Node a3 (x ': xs)) :: a2 -> Type)

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)

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)

Unfold for a Tree.

Example

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

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)

Unfold for a Forest.

Instances

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

Defined in Fcf.Data.Tree

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

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

Flatten a Tree.

Example

>>> :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)

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

Get the root node from a Tree.

Instances

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

Defined in Fcf.Data.Tree

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

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

Get the forest from a Tree.

Instances

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

Defined in Fcf.Data.Tree

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

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

Get the root nodes from a list of Trees.

Instances

type Eval (GetRoots trs :: [b] -> Type)

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]

Get the forests from a list of Trees.

Instances

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

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

Instances

type Eval (SubFLevels (t ': ts) :: Maybe ([a], [Tree a]) -> Type)

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)

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

Get the levels from a Tree.

Example

>>> :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)

Defined in Fcf.Data.Tree

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