Copyright	(c) gspia 2020-
License	BSD
Maintainer	gspia
Safe Haskell	Safe-Inferred
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]
type ExT1r = 'Node 1 '['Node 2 '['Node 3 '['Node 4 '[]]], 'Node 5 '['Node 6 '[]]]
type ExTr2 = 'Node ('Just 1) '['Node ('Just 2) '['Node ('Just 3) '['Node ('Just 4) '[]]], 'Node ('Just 5) '['Node ('Just 6) '[]]]
data StarTx :: Tree a -> Tree (a -> Exp b) -> Exp (Tree b)
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

Instances details

(KnownVal val k, KnownVal (Forest val) trees) => KnownVal (Tree val) ('Node k trees :: Tree a) Source #
Instance details Defined in Fcf.Data.Reflect Methods fromType :: Proxy ('Node k trees) -> Tree0 val Source #
type Eval (FoldTree f ('Node a3 (x ': xs)) :: a1 -> Type) Source #
Instance details Defined in Fcf.Data.Tree type Eval (FoldTree f ('Node a3 (x ': xs)) :: a1 -> Type) = Eval (f a3 (Eval (Map (FoldTree f) (x ': xs))))
type Eval (FoldTree f ('Node a3 ('[] :: [Tree a2])) :: a1 -> Type) Source #
Instance details Defined in Fcf.Data.Tree type Eval (FoldTree f ('Node a3 ('[] :: [Tree a2])) :: a1 -> Type) = Eval (f a3 ('[] :: [a1]))
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 (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 (GetForest ('Node _1 f) :: [Tree a] -> Type) Source #
Instance details Defined in Fcf.Data.Tree type Eval (GetForest ('Node _1 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 (Return a2 :: Tree a1 -> Type) Source #
Instance details Defined in Fcf.Data.Tree type Eval (Return a2 :: Tree a1 -> Type) = 'Node a2 ('[] :: [Tree 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 Eval (StarTx fa fab :: Tree b -> Type) Source #
Instance details Defined in Fcf.Data.Tree type Eval (StarTx fa fab :: Tree b -> Type) = Eval (fab <*> fa)
type Eval ('Node f tfs <*> 'Node x txs :: Tree b -> Type) Source #
Instance details Defined in Fcf.Data.Tree type Eval ('Node f tfs <*> 'Node x txs :: Tree b -> Type) = 'Node (Eval (f x)) (Eval (Eval (Map (Map f :: Tree a -> Tree b -> Type) txs) ++ Eval (Map (StarTx ('Node x txs) :: Tree (a -> Exp b) -> Tree b -> Type) tfs)))
type Eval (Map f ('Node a2 tr) :: Tree b -> Type) Source #
Instance details Defined in Fcf.Data.Tree type Eval (Map f ('Node a2 tr) :: Tree b -> Type) = 'Node (f @@ a2) (Eval (Map (Map f :: Tree a1 -> Tree b -> Type) tr))
type Eval (Traverse f2 ('Node x ts) :: f1 (Tree b) -> Type) Source #
Instance details Defined in Fcf.Data.Tree type Eval (Traverse f2 ('Node x ts) :: f1 (Tree b) -> Type) = Eval (LiftA2 (Pure2 ('Node :: b -> [Tree b] -> Tree b)) (Eval (f2 x)) (Eval (Traverse (Traverse f2 :: Tree a -> f1 (Tree b) -> Type) ts)))

type Forest a = [Tree a] Source #

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

type ExT1r = 'Node 1 '['Node 2 '['Node 3 '['Node 4 '[]]], 'Node 5 '['Node 6 '[]]] Source #

type ExTr2 = 'Node ('Just 1) '['Node ('Just 2) '['Node ('Just 3) '['Node ('Just 4) '[]]], 'Node ('Just 5) '['Node ('Just 6) '[]]] Source #

data StarTx :: Tree a -> Tree (a -> Exp b) -> Exp (Tree b) Source #

Instances

Instances details

type Eval (StarTx fa fab :: Tree b -> Type) Source #
Instance details Defined in Fcf.Data.Tree type Eval (StarTx fa fab :: Tree b -> Type) = Eval (fab <*> fa)

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

Fold a type-level Tree.

Instances

Instances details

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

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 TL.Natural
= 'Node
    1
    '[ 'Node 2 '[ 'Node 4 '[], 'Node 5 '[]],
       'Node 3 '[ 'Node 6 '[], 'Node 7 '[]]]

Instances

Instances details

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

Instances details

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 '[]]])) :: [TL.Natural]
= '[1, 2, 3, 4, 5, 6]

Instances

Instances details

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

Instances details

type Eval (GetRoot ('Node a2 _1) :: a1 -> Type) Source #
Instance details Defined in Fcf.Data.Tree type Eval (GetRoot ('Node a2 _1) :: a1 -> Type) = a2

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

Get the forest from a Tree.

Instances

Instances details

type Eval (GetForest ('Node _1 f) :: [Tree a] -> Type) Source #
Instance details Defined in Fcf.Data.Tree type Eval (GetForest ('Node _1 f) :: [Tree a] -> Type) = f

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

Get the root nodes from a list of Trees.

Instances

Instances details

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

Instances details

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

Instances details

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 '[]]])) :: [[TL.Natural]]
= '[ '[1], '[2, 5], '[3, 6], '[4]]

Instances

Instances details

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