Copyright	(c) gspia 2020-
License	BSD
Maintainer	gspia
Safe Haskell	Safe
Language	Haskell2010

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

data Tree a = Node a [Tree a]
type Forest a = [Tree a]
data FoldTree :: (a -> [b] -> Exp b) -> Tree a -> Exp b
data UnfoldTree :: (b -> Exp (a, [b])) -> b -> Exp (Tree a)
data UnfoldForest :: (b -> Exp (a, [b])) -> [b] -> Exp (Forest a)
data Flatten :: Tree a -> Exp [a]
data GetRoot :: Tree a -> Exp a
data GetForest :: Tree a -> Exp [Tree a]
data GetRoots :: [Tree a] -> Exp [a]
data GetForests :: [Tree a] -> Exp [Tree a]
data SubFLevels :: [Tree a] -> Exp (Maybe ([a], [Tree a]))
data Levels :: Tree a -> Exp [[a]]

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

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

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

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