fcf-containers-0.4.0: Data structures and algorithms for first-class-families

Fcf.Alg.Tree

Description

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

Synopsis

# Documentation

data TreeF a b Source #

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

Constructors

 NodeF a [b]
Instances
 type Eval (FSum (NodeF a2 (b ': bs)) :: Nat -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (FSum (NodeF a2 (b ': bs)) :: Nat -> Type) = Eval (Sum (b ': bs)) type Eval (FSum (NodeF a2 ([] :: [Nat])) :: Nat -> Type) Source # Instances to make TreeF to be a foldable sum. After this one, we can write the Sizes example. Instance detailsDefined in Fcf.Alg.Tree type Eval (FSum (NodeF a2 ([] :: [Nat])) :: Nat -> Type) = 0 type Eval (TreeToFix (Node a2 (b ': bs)) :: Fix (TreeF a1) -> Type) Source # Instance detailsDefined 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 detailsDefined in Fcf.Alg.Tree type Eval (TreeToFix (Node a2 ([] :: [Tree a1])) :: Fix (TreeF a1) -> Type) = Fix (NodeF a2 ([] :: [Fix (TreeF a1)])) type Eval (BuildFibTreeCoA n :: TreeF Nat Nat -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (BuildFibTreeCoA n :: TreeF Nat Nat -> Type) = If (Eval (n >= 2)) (NodeF 0 ((n - 1) ': ((n - 2) ': ([] :: [Nat])))) (NodeF n ([] :: [Nat])) type Eval (BuildNodeCoA n :: TreeF Nat Nat -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (BuildNodeCoA n :: TreeF Nat Nat -> Type) = If (Eval (((2 * n) + 1) >= 8)) (NodeF n ([] :: [Nat])) (NodeF n ((2 * n) ': (((2 * n) + 1) ': ([] :: [Nat])))) type Eval (Map f (NodeF a3 (b2 ': bs)) :: TreeF a2 b1 -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (Map f (NodeF a3 (b2 ': bs)) :: TreeF a2 b1 -> Type) = NodeF a3 (Eval (Map f (b2 ': bs))) type Eval (Map f (NodeF a3 ([] :: [a1])) :: TreeF a2 b -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (Map f (NodeF a3 ([] :: [a1])) :: TreeF a2 b -> Type) = NodeF a3 ([] :: [b])

data TreeToFix :: Tree a -> Exp (Fix (TreeF a)) Source #

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.

Instances
 type Eval (TreeToFix (Node a2 (b ': bs)) :: Fix (TreeF a1) -> Type) Source # Instance detailsDefined 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 detailsDefined in Fcf.Alg.Tree type Eval (TreeToFix (Node a2 ([] :: [Tree a1])) :: Fix (TreeF a1) -> Type) = Fix (NodeF a2 ([] :: [Fix (TreeF a1)]))

Sum the nodes of TreeF containing Nats.

See the implementation of Fib for an example.

Instances
 type Eval (SumNodesAlg (NodeF x (b ': bs)) :: Nat -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (SumNodesAlg (NodeF x (b ': bs)) :: Nat -> Type) = x + Eval (Sum (b ': bs)) type Eval (SumNodesAlg (NodeF x ([] :: [Nat])) :: Nat -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (SumNodesAlg (NodeF x ([] :: [Nat])) :: Nat -> Type) = x

data CountNodesAlg :: Algebra (TreeF a) Nat Source #

Count the nodes of TreeF.

See the Size for an example.

Instances
 type Eval (CountNodesAlg (NodeF x (b ': bs)) :: Nat -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (CountNodesAlg (NodeF x (b ': bs)) :: Nat -> Type) = 1 + Eval (Sum (b ': bs)) type Eval (CountNodesAlg (NodeF x ([] :: [Nat])) :: Nat -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (CountNodesAlg (NodeF x ([] :: [Nat])) :: Nat -> Type) = 1

data Size :: Tree a -> Exp Nat Source #

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

Instances
 type Eval (Size tr :: Nat -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (Size tr :: Nat -> Type) = Eval (Cata (CountNodesAlg :: TreeF a Nat -> Nat -> Type) =<< TreeToFix tr)

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)

Instances
 type Eval (BuildNodeCoA n :: TreeF Nat Nat -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (BuildNodeCoA n :: TreeF Nat Nat -> Type) = If (Eval (((2 * n) + 1) >= 8)) (NodeF n ([] :: [Nat])) (NodeF n ((2 * n) ': (((2 * n) + 1) ': ([] :: [Nat]))))

CoAlgebra for the Fib-function.

Instances
 type Eval (BuildFibTreeCoA n :: TreeF Nat Nat -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (BuildFibTreeCoA n :: TreeF Nat Nat -> Type) = If (Eval (n >= 2)) (NodeF 0 ((n - 1) ': ((n - 2) ': ([] :: [Nat])))) (NodeF n ([] :: [Nat]))

data FibHylo :: Nat -> Exp Nat Source #

Fibonaccis with Hylo, not efficient

Example

>>> :kind! Eval (FibHylo 10)
Eval (FibHylo 10) :: Nat
= 55

Instances
 type Eval (FibHylo n :: Nat -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (FibHylo n :: Nat -> Type) = Eval (Hylo SumNodesAlg BuildFibTreeCoA n)

data BTreeF a b Source #

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

Constructors

 BEmptyF BNodeF a b b
Instances
 type Eval (PartHlp smaller (h ': t) :: BTreeF a [a] -> Type) Source # Instance detailsDefined in Fcf.Alg.Sort type Eval (PartHlp smaller (h ': t) :: BTreeF a [a] -> Type) = BNodeF h (Eval (Filter (smaller h) t)) (Eval (Filter (Not <=< smaller h) t)) type Eval (PartHlp _ ([] :: [a]) :: BTreeF a [a] -> Type) Source # Instance detailsDefined in Fcf.Alg.Sort type Eval (PartHlp _ ([] :: [a]) :: BTreeF a [a] -> Type) = (BEmptyF :: BTreeF a [a]) type Eval (PartCmp cmp coalg :: BTreeF a [a] -> Type) Source # Instance detailsDefined in Fcf.Alg.Sort type Eval (PartCmp cmp coalg :: BTreeF a [a] -> Type) = Eval (PartHlp (Flip cmp) coalg) type Eval (Map f (BNodeF a4 b1 b2) :: BTreeF a3 a2 -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (Map f (BNodeF a4 b1 b2) :: BTreeF a3 a2 -> Type) = BNodeF a4 (Eval (f b1)) (Eval (f b2)) type Eval (Map f (BEmptyF :: BTreeF a2 a1) :: BTreeF a2 b -> Type) Source # BTreeF is a functor Instance detailsDefined in Fcf.Alg.Tree type Eval (Map f (BEmptyF :: BTreeF a2 a1) :: BTreeF a2 b -> Type) = (BEmptyF :: BTreeF a2 b)

data FSum :: f a -> Exp a Source #

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

Instances
 type Eval (FSum (NodeF a2 (b ': bs)) :: Nat -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (FSum (NodeF a2 (b ': bs)) :: Nat -> Type) = Eval (Sum (b ': bs)) type Eval (FSum (NodeF a2 ([] :: [Nat])) :: Nat -> Type) Source # Instances to make TreeF to be a foldable sum. After this one, we can write the Sizes example. Instance detailsDefined in Fcf.Alg.Tree type Eval (FSum (NodeF a2 ([] :: [Nat])) :: Nat -> Type) = 0

data Sizes :: Fix f -> Exp (Ann f Nat) Source #

Instances
 type Eval (Sizes fx :: Ann f Nat -> Type) Source # 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 Nat) Nat) = '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))  Instance detailsDefined in Fcf.Alg.Tree type Eval (Sizes fx :: Ann f Nat -> Type) = Eval (Synthesize ((+) 1 <=< (FSum :: f Nat -> Nat -> Type)) fx)

data NatF r Source #

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
Instances
 type Eval (FibAlgebra (Succ (Fix (AnnF ((,) (Succ (Fix (AnnF ((,) _ n)))) m)))) :: Nat -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (FibAlgebra (Succ (Fix (AnnF ((,) (Succ (Fix (AnnF ((,) _ n)))) m)))) :: Nat -> Type) = Eval (n + m) type Eval (FibAlgebra (Succ (Fix (AnnF ((,) (Zero :: NatF (Fix (AnnF NatF Nat))) _)))) :: Nat -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (FibAlgebra (Succ (Fix (AnnF ((,) (Zero :: NatF (Fix (AnnF NatF Nat))) _)))) :: Nat -> Type) = 1 type Eval (FibAlgebra (Zero :: NatF (Ann NatF Nat))) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (FibAlgebra (Zero :: NatF (Ann NatF Nat))) = 0 type Eval (RecNTF n :: Fix NatF -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (RecNTF n :: Fix NatF -> Type) = Fix (Succ (Eval (NatToFix n))) type Eval (NatToFix n :: Fix NatF -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (NatToFix n :: Fix NatF -> Type) = Eval (If (Eval (n < 1)) (Pure (Fix (Zero :: NatF (Fix NatF)))) (RecNTF =<< (n - 1))) type Eval (Map f (Succ r2) :: NatF r1 -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (Map f (Succ r2) :: NatF r1 -> Type) = Succ (Eval (f r2)) type Eval (Map f (Zero :: NatF a) :: NatF b -> Type) Source # NatF has to have functor-instances so that morphisms will work. Instance detailsDefined in Fcf.Alg.Tree type Eval (Map f (Zero :: NatF a) :: NatF b -> Type) = (Zero :: NatF b)

data NatToFix :: Nat -> Exp (Fix NatF) Source #

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

Instances
 type Eval (NatToFix n :: Fix NatF -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (NatToFix n :: Fix NatF -> Type) = Eval (If (Eval (n < 1)) (Pure (Fix (Zero :: NatF (Fix NatF)))) (RecNTF =<< (n - 1)))

data RecNTF :: Nat -> Exp (Fix NatF) Source #

Instances
 type Eval (RecNTF n :: Fix NatF -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (RecNTF n :: Fix NatF -> Type) = Fix (Succ (Eval (NatToFix n)))

data FibAlgebra :: NatF (Ann NatF Nat) -> Exp Nat Source #

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

Instances
 type Eval (FibAlgebra (Succ (Fix (AnnF ((,) (Succ (Fix (AnnF ((,) _ n)))) m)))) :: Nat -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (FibAlgebra (Succ (Fix (AnnF ((,) (Succ (Fix (AnnF ((,) _ n)))) m)))) :: Nat -> Type) = Eval (n + m) type Eval (FibAlgebra (Succ (Fix (AnnF ((,) (Zero :: NatF (Fix (AnnF NatF Nat))) _)))) :: Nat -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (FibAlgebra (Succ (Fix (AnnF ((,) (Zero :: NatF (Fix (AnnF NatF Nat))) _)))) :: Nat -> Type) = 1 type Eval (FibAlgebra (Zero :: NatF (Ann NatF Nat))) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (FibAlgebra (Zero :: NatF (Ann NatF Nat))) = 0

data FibHisto :: Nat -> Exp Nat Source #

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

Example

>>> :kind! Eval (FibHisto 100)
Eval (FibHisto 100) :: Nat
= 354224848179261915075

Instances
 type Eval (FibHisto n :: Nat -> Type) Source # Instance detailsDefined in Fcf.Alg.Tree type Eval (FibHisto n :: Nat -> Type) = Eval (Histo FibAlgebra =<< NatToFix n)