Modulefcf-containers-0.8.2Haskell2010

Fcf.Alg.Tree

Type-level TreeF and BTreeF to be used with Cata, Ana and Hylo. This also provides some algorithms: general purpose sorting with Qsort, Size of an Tree, Fibonaccis.

16 types

Packagefcf-containers-0.8.2
Exports16
LanguageHaskell2010
LicenceBSD-3-Clause
SourceTree.hs

datadata TreeF a b

TreeF is functor for Trees. TreeF has Map-instance (on structure).

Constructors

NodeF a [b]

Instances8Eval, …

type Eval (BuildFibTreeCoA n) = If (Eval (n >= 2)) ('NodeF 0 '[n - 1, n - 2]) ('NodeF n '[])Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
type Eval (BuildNodeCoA n) = If (Eval (((2 * n) + 1) >= 8)) ('NodeF n '[]) ('NodeF n '[2 * n, (2 * n) + 1])Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
type Eval (FSum ('NodeF a2 '[])) = 0Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
Instances to make TreeF to be a foldable sum. After this one, we can write the Sizes example.
type Eval (FSum ('NodeF a2 (b ': bs))) = Eval (Sum (b ': bs))Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
type Eval (TreeToFix ('Node a2 '[])) = 'Fix ('NodeF a2 '[])Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
type Eval (TreeToFix ('Node a2 (b ': bs))) = 'Fix ('NodeF a2 (Eval (Map TreeToFix (b ': bs))))Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
type Eval (Map f ('NodeF a3 '[])) = 'NodeF a3 '[]Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
type Eval (Map f ('NodeF a3 (b2 ': bs))) = 'NodeF a3 (Eval (Map f (b2 ': bs)))Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree

datadata TreeToFix (b :: Tree a) (c :: Fix (TreeF a))

A function to transform a Tree into fixed structure that can be used by Cata and Ana.

See the implementation of Size for an example.

Instances2Eval

type Eval (TreeToFix ('Node a2 '[])) = 'Fix ('NodeF a2 '[])Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
type Eval (TreeToFix ('Node a2 (b ': bs))) = 'Fix ('NodeF a2 (Eval (Map TreeToFix (b ': bs))))Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree

datadata SumNodesAlg (a :: TreeF Nat Nat) (b :: Nat)

Sum the nodes of TreeF containing Nats.

See the implementation of Fib for an example.

Instances2Eval

type Eval (SumNodesAlg ('NodeF x '[])) = xDefined in fcf-containers-0.8.2 · Fcf.Alg.Tree
type Eval (SumNodesAlg ('NodeF x (b ': bs))) = x + Eval (Sum (b ': bs))Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree

datadata CountNodesAlg (b :: TreeF a Nat) (c :: Nat)

Count the nodes of TreeF.

See the Size for an example.

Instances2Eval

type Eval (CountNodesAlg ('NodeF x '[])) = 1Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
type Eval (CountNodesAlg ('NodeF x (b ': bs))) = 1 + Eval (Sum (b ': bs))Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree

datadata Size (b :: Tree a) (c :: Nat)

Size of the Tree is the number of nodes in it.

Example

Size is defined as Cata CountNodesAlg =<< TreeToFix tr and can be used with the following.

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 (Size =<< UnfoldTree BuildNode 1)

Eval (Size =<< UnfoldTree BuildNode 1) :: TL.Natural = 7

Instances1Eval

type Eval (Size tr) = Eval (Cata CountNodesAlg =<< TreeToFix tr)Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree

datadata BuildNodeCoA (a :: Nat) (b :: TreeF Nat Nat)

CoAlgebra to build TreeF's. This is an example from containers-package. See Size and example in there.

:kind! Eval (Ana BuildNodeCoA 1) :kind! Eval (Hylo CountNodesAlg BuildNodeCoA 1)

Instances1Eval

type Eval (BuildNodeCoA n) = If (Eval (((2 * n) + 1) >= 8)) ('NodeF n '[]) ('NodeF n '[2 * n, (2 * n) + 1])Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree

datadata BuildFibTreeCoA (a :: Nat) (b :: TreeF Nat Nat)

CoAlgebra for the Fib-function.

Instances1Eval

type Eval (BuildFibTreeCoA n) = If (Eval (n >= 2)) ('NodeF 0 '[n - 1, n - 2]) ('NodeF n '[])Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree

datadata FibHylo (a :: Nat) (b :: Nat)

Fibonaccis with Hylo, not efficient

Example

:kind! Eval (FibHylo 10)

Eval (FibHylo 10) :: TL.Natural = 55

Instances1Eval

type Eval (FibHylo n) = Eval (Hylo SumNodesAlg BuildFibTreeCoA n)Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree

datadata BTreeF a b

BTreeF is a btree functor. At the moment, it is used to build sorting algorithms.

Constructors

BEmptyF
BNodeF a b b

Instances5Eval

type Eval (PartCmp cmp coalg) = Eval (PartHlp (Flip cmp) coalg)Defined in fcf-containers-0.8.2 · Fcf.Alg.Sort
type Eval (PartHlp _1 '[]) = 'BEmptyFDefined in fcf-containers-0.8.2 · Fcf.Alg.Sort
type Eval (PartHlp smaller (h ': t)) = 'BNodeF h (Eval (Filter (smaller h) t)) (Eval (Filter (Not <=< smaller h) t))Defined in fcf-containers-0.8.2 · Fcf.Alg.Sort
type Eval (Map f 'BEmptyF) = 'BEmptyFDefined in fcf-containers-0.8.2 · Fcf.Alg.Tree
BTreeF is a functor
type Eval (Map f ('BNodeF a4 b1 b2)) = 'BNodeF a4 (Eval (f b1)) (Eval (f b2))Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree

datadata FSum (b :: f a) (c :: a)

A kind of foldable sum class. Pun may or may not be intended.

Instances2Eval

type Eval (FSum ('NodeF a2 '[])) = 0Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
Instances to make TreeF to be a foldable sum. After this one, we can write the Sizes example.
type Eval (FSum ('NodeF a2 (b ': bs))) = Eval (Sum (b ': bs))Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree

datadata Sizes (a :: Fix f) (b :: Ann f Nat)

Instances1Eval

type Eval (Sizes fx) = Eval (Synthesize ((+) 1 <=< FSum) fx)Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
Sizes example from Recursion Schemes by example, Tim Williams. This annotes each node with the size of its subtree.
Example
```
:kind! Eval (Sizes =<< Ana BuildNodeCoA 1)
```
Eval (Sizes =<< Ana BuildNodeCoA 1) :: Fix (AnnF (TreeF TL.Natural) TL.Natural) = 'Fix ('AnnF '( 'NodeF 1 '[ 'Fix ('AnnF '( 'NodeF 2 '[ 'Fix ('AnnF '( 'NodeF 4 '[], 1)), 'Fix ('AnnF '( 'NodeF 5 '[], 1))], 3)), 'Fix ('AnnF '( 'NodeF 3 '[ 'Fix ('AnnF '( 'NodeF 6 '[], 1)), 'Fix ('AnnF '( 'NodeF 7 '[], 1))], 3))], 7))

datadata NatF r

A NatF functor that can be used with different morphisms. This tree-module is probably a wrong place to this one. Now it is here for the Fibonacci example.

Constructors

Succ r
Zero

Instances7Eval, …

type Eval (FibAlgebra 'Zero) = 0Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
type Eval (FibAlgebra ('Succ ('Fix ('AnnF '('Succ ('Fix ('AnnF '(_1, n))), m))))) = Eval (n + m)Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
type Eval (FibAlgebra ('Succ ('Fix ('AnnF '('Zero, _1))))) = 1Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
type Eval (NatToFix n) = Eval (If (Eval (n < 1)) (Pure ('Fix 'Zero)) (RecNTF =<< (n - 1)))Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
type Eval (RecNTF n) = 'Fix ('Succ (Eval (NatToFix n)))Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
type Eval (Map f 'Zero) = 'ZeroDefined in fcf-containers-0.8.2 · Fcf.Alg.Tree
NatF has to have functor-instances so that morphisms will work.
type Eval (Map f ('Succ r2)) = 'Succ (Eval (f r2))Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree

datadata NatToFix (a :: Nat) (b :: Fix NatF)

We want to be able to build NatF Fix-structures out of Nat's.

Instances1Eval

type Eval (NatToFix n) = Eval (If (Eval (n < 1)) (Pure ('Fix 'Zero)) (RecNTF =<< (n - 1)))Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree

datadata RecNTF (a :: Nat) (b :: Fix NatF)

Instances1Eval

type Eval (RecNTF n) = 'Fix ('Succ (Eval (NatToFix n)))Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree

datadata FibAlgebra (a :: NatF (Ann NatF Nat)) (b :: Nat)

Efficient Fibonacci algebra from Recursion Schemes by example, Tim Williams.

Instances3Eval

type Eval (FibAlgebra 'Zero) = 0Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
type Eval (FibAlgebra ('Succ ('Fix ('AnnF '('Succ ('Fix ('AnnF '(_1, n))), m))))) = Eval (n + m)Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree
type Eval (FibAlgebra ('Succ ('Fix ('AnnF '('Zero, _1))))) = 1Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree

datadata FibHisto (a :: Nat) (b :: Nat)

Efficient Fibonacci type-level function (from Recursion Schemes by example, Tim Williams). Compare this to FibHylo.

Example

:kind! Eval (FibHisto 100)

Eval (FibHisto 100) :: TL.Natural = 354224848179261915075

Instances1Eval

type Eval (FibHisto n) = Eval (Histo FibAlgebra =<< NatToFix n)Defined in fcf-containers-0.8.2 · Fcf.Alg.Tree