Copyright | (c) gspia 2020- |
---|---|

License | BSD |

Maintainer | gspia |

Safe Haskell | Safe |

Language | Haskell2010 |

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

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

#### Instances

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

type Eval (FoldTree f ('Node a3 ('[] :: [Tree a1])) :: a2 -> Type) Source # | |

type Eval (GetForest ('Node _1 f) :: [Tree a] -> Type) Source # | |

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

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

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

Defined in Fcf.Data.Tree | |

type Eval (TreeToFix ('Node a2 (b ': bs)) :: Fix (TreeF a1) -> Type) Source # | |

type Eval (TreeToFix ('Node a2 ('[] :: [Tree a1])) :: Fix (TreeF a1) -> Type) Source # | |

type Eval (UnfoldForest f bs :: Forest a2 -> Type) Source # | |

Defined in Fcf.Data.Tree | |

type Eval (UnfoldTree f b2 :: Tree a -> Type) Source # | |

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`

.

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 ]) :}`:{`

`>>>`

Eval (UnfoldTree BuildNode 1) :: Tree Nat = 'Node 1 '[ 'Node 2 '[ 'Node 4 '[], 'Node 5 '[]], 'Node 3 '[ 'Node 6 '[], 'Node 7 '[]]]`:kind! Eval (UnfoldTree BuildNode 1)`

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

Unfold for a `Forest`

.

#### Instances

type Eval (UnfoldForest f bs :: Forest a2 -> Type) Source # | |

Defined in Fcf.Data.Tree |

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

Flatten a `Tree`

.

### Example

`>>>`

Eval (Flatten ('Node 1 '[ 'Node 2 '[ 'Node 3 '[ 'Node 4 '[]]], 'Node 5 '[ 'Node 6 '[]]])) :: [Nat] = '[1, 2, 3, 4, 5, 6]`:kind! Eval (Flatten ('Node 1 '[ 'Node 2 '[ 'Node 3 '[ 'Node 4 '[]]], 'Node 5 '[ 'Node 6 '[]]]))`

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

#### Instances

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

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

Defined in Fcf.Data.Tree |

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

Get the levels from a `Tree`

.

### Example

`>>>`

Eval (Levels ('Node 1 '[ 'Node 2 '[ 'Node 3 '[ 'Node 4 '[]]], 'Node 5 '[ 'Node 6 '[]]])) :: [[Nat]] = '[ '[1], '[2, 5], '[3, 6], '[4]]`:kind! Eval (Levels ('Node 1 '[ 'Node 2 '[ 'Node 3 '[ 'Node 4 '[]]], 'Node 5 '[ 'Node 6 '[]]]))`