Fcf.Alg.Tree

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.

Documentation

data TreeF a b

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

Constructors

NodeF a [b]

Instances

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

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)

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

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

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

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

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

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)

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)

Defined in Fcf.Alg.Tree

type Eval (TreeToFix (Node a2 ([] :: [Tree a1])) :: Fix (TreeF a1) -> Type) = Fix (NodeF a2 ([] :: [Fix (TreeF a1)]))

data SumNodesAlg :: Algebra (TreeF Nat) Nat

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)

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

Defined in Fcf.Alg.Tree

type Eval (SumNodesAlg (NodeF x ([] :: [Nat])) :: Nat -> Type) = x

data CountNodesAlg :: Algebra (TreeF a) Nat

Count the nodes of TreeF.

See the Size for an example.

Instances

type Eval (CountNodesAlg (NodeF x (b ': bs)) :: Nat -> Type)

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

Defined in Fcf.Alg.Tree

type Eval (CountNodesAlg (NodeF x ([] :: [Nat])) :: Nat -> Type) = 1

data Size :: Tree a -> Exp 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) :: Nat
= 7

Instances

type Eval (Size tr :: Nat -> Type)

Defined in Fcf.Alg.Tree

type Eval (Size tr :: Nat -> Type) = Eval (Cata (CountNodesAlg :: TreeF a Nat -> Nat -> Type) =<< TreeToFix tr)

data BuildNodeCoA :: CoAlgebra (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)

Instances

type Eval (BuildNodeCoA n :: TreeF Nat Nat -> Type)

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

data BuildFibTreeCoA :: CoAlgebra (TreeF Nat) Nat

CoAlgebra for the Fib-function.

Instances

type Eval (BuildFibTreeCoA n :: TreeF Nat Nat -> Type)

Defined 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 Fib :: Nat -> Exp Nat

Fibonaccis with Hylo, not efficient

Example

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

Instances

type Eval (Fib n :: Nat -> Type)

Defined in Fcf.Alg.Tree

type Eval (Fib n :: Nat -> Type) = Eval (Hylo SumNodesAlg BuildFibTreeCoA n)

data BTreeF a b

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)

Defined in Fcf.Alg.Tree

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)

Defined in Fcf.Alg.Tree

type Eval (PartHlp _ ([] :: [a]) :: BTreeF a [a] -> Type) = (BEmptyF :: BTreeF a [a])

type Eval (PartCmp cmp coalg :: BTreeF a [a] -> Type)

Defined in Fcf.Alg.Tree

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)

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

Defined in Fcf.Alg.Tree

type Eval (Map f (BEmptyF :: BTreeF a2 a1) :: BTreeF a2 b -> Type) = (BEmptyF :: BTreeF a2 b)

data PartHlp :: (a -> a -> Exp Bool) -> CoAlgebra (BTreeF a) [a]

Instances

type Eval (PartHlp smaller (h ': t) :: BTreeF a [a] -> Type)

Defined in Fcf.Alg.Tree

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)

Defined in Fcf.Alg.Tree

type Eval (PartHlp _ ([] :: [a]) :: BTreeF a [a] -> Type) = (BEmptyF :: BTreeF a [a])

data SymbolCompareInc :: Symbol -> Symbol -> Exp Bool

Use this if you want to sort symbols into increasing order.

Instances

type Eval (SymbolCompareInc n1 n2 :: Bool -> Type)

Defined in Fcf.Alg.Tree

type Eval (SymbolCompareInc n1 n2 :: Bool -> Type) = Eval (TyEq (CmpSymbol n1 n2) LT)

data SymbolCompareDec :: Symbol -> Symbol -> Exp Bool

Use this if you want to sort symbols into decreasing order.

Instances

type Eval (SymbolCompareDec n1 n2 :: Bool -> Type)

Defined in Fcf.Alg.Tree

type Eval (SymbolCompareDec n1 n2 :: Bool -> Type) = Eval (TyEq (CmpSymbol n1 n2) GT)

data Inord :: Algebra (BTreeF a) [a]

Instances

type Eval (Inord (BNodeF v l r) :: [a] -> Type)

Defined in Fcf.Alg.Tree

type Eval (Inord (BNodeF v l r) :: [a] -> Type) = Eval (l ++ Eval ((v ': ([] :: [a])) ++ r))

type Eval (Inord (BEmptyF :: BTreeF a [a]) :: [a] -> Type)

Defined in Fcf.Alg.Tree

type Eval (Inord (BEmptyF :: BTreeF a [a]) :: [a] -> Type) = ([] :: [a])

data Qsort :: (a -> a -> Exp Bool) -> [a] -> Exp [a]

Qsort - give the comparison function a -> a -> Exp Bool comparing your list elements and then Qsort will order the list.

Example

>>> :kind! Eval (Qsort (<) '[5,3,1,9,4,6,3])
Eval (Qsort (<) '[5,3,1,9,4,6,3]) :: [Nat]
= '[1, 3, 3, 4, 5, 6, 9]

>>> :kind! Eval (Qsort SymbolCompareInc '[ "bb", "e", "a", "e", "d" ])
Eval (Qsort SymbolCompareInc '[ "bb", "e", "a", "e", "d" ]) :: [TL.Symbol]
= '["a", "bb", "d", "e", "e"]

Instances

type Eval (Qsort cmp lst :: [a] -> Type)

Defined in Fcf.Alg.Tree

type Eval (Qsort cmp lst :: [a] -> Type) = Eval (Hylo (Inord :: BTreeF a [a] -> [a] -> Type) (PartCmp cmp) lst)

data PartCmp :: (a -> a -> Exp Bool) -> CoAlgebra (BTreeF a) [a]

Instances

type Eval (PartCmp cmp coalg :: BTreeF a [a] -> Type)

Defined in Fcf.Alg.Tree

type Eval (PartCmp cmp coalg :: BTreeF a [a] -> Type) = Eval (PartHlp (Flip cmp) coalg)