The number of binary partitions for a number n is the number of unique ways to partition this number (ignoring the order) into powers of 2. | Definition of the binary partitioning of a number as an hylomorphism.

type BTree = K One :+!: (I :+!: (I :*!: I))Source

The fixpoint of the functor representing trees with maximal branching factor of two.

bpHylo :: Int -> Int Source

Definition of the binary partitioning of a number as an hylomorphism.

bpDyna :: Int -> Int Source

Definition of the binary partitioning of a number as a dynamorphism.

Average

average :: [Int] -> Int Source

Recursive definition of the average of a set of integers.

averageCata :: [Int] -> Int Source

Definition of the average of a set of integers as a catamorphism.

Lists

Singleton list.

wrap :: a -> [a]Source

Pre-defined wrapping of an element into a list.

wrapPF :: a -> [a]Source

Definition of wrapping in the point-free style.

Tail

tail :: [a] -> [a]Source

Definition of the tail of a list as a total function.

tailPF :: [a] -> [a]Source

Definition of the tail of a list in the point-free style.

tailCata :: [a] -> [a]Source

Definition of the tail of a list as an anamorphism.

tailPara :: [a] -> [a]Source

Definition of the tail of a list as a paramorphism.

Length

length :: [a] -> Int Source

Native recursion definition of list length.

lengthPF :: [a] -> Int Source

Recursive definition of list length in the point-free style.

lengthPF' :: [a] -> Int Source

Recursive definition of list length in the point-free style with structural recursion.

lengthHylo :: [a] -> Int Source

Definition of list length as an hylomorphism.

lengthAna :: [a] -> Int Source

Definition of list length as an anamorphism.

lengthCata :: [a] -> Int Source

Definition of list length as a catamorphism.

Filtering

filter :: (a -> Bool) -> [a] -> [a]Source

Native recursive definition of list filtering.

filterCata :: (a -> Bool) -> [a] -> [a]Source

Definition of list filtering as an catamorphism.

Generation

repeatAna :: a -> [a]Source

Generation of infinite lists as an anamorphism.

replicateAna :: (Int, a) -> [a]Source

Finite replication of an element as an anamorphism.

downtoAna :: Int -> [Int]Source

Generation of a downwards list as an anamorphism.

insertApo :: Ord a => (a, [a]) -> [a]Source

Ordered list insertion as an apomorphism.

insertPara :: Ord a => (a, [a]) -> [a]Source

Ordered list insertion as a paramorphism.

snoc :: (a, [a]) -> [a]Source

Append an element to the end of a list as an hylomorphism.

snocApo :: (a, [a]) -> [a]Source

Append an element to the end of a list as an apomorphism.

Extraction

bubble :: Ord a => [a] -> Either One (a, [a])Source

Creates a bubble from a list. Used in the bubble sort algorithm.

takeAna :: (Int, [a]) -> [a]Source

Extraction of a number of elements from a list as an anamorphism.

Partition

partition :: Ord a => (a, [a]) -> ([a], [a])Source

Native recursive definition for partitioning a list at a specified element.

partitionHylo :: Ord a => (a, [a]) -> ([a], [a])Source

Definition for partitioning a list at a specified element as an hylomorphism.

Transformations

isum :: [Int] -> [Int]Source

Incremental summation as a catamorphism.

fisum :: [Int] -> Int -> [Int]Source

Incrementation the elements of a list by a specified value as a catamorphism.

data Some a Source

Constructors

Wrap a
Insert a (Some a)

Instances

Eq a => Eq (Some a)
Show a => Show (Some a)
Mu (Some a)

isumsAccum :: ([Int], Int) -> Some Int Source

Incrementation the elements of a list by a specified value as an accumulation. The result is always a non-empty list

isumsAna :: ([Int], Int) -> Some Int Source

mapCata :: [a] -> (a -> b) -> [b]Source

Definition of list mapping as a catamorphism.

reverseCata :: [a] -> [a]Source

Definition of list reversion as a catamorphism.

reverseAccum' :: ([a], [a]) -> [a]Source

Linear version of reverse using accumulations

reverseHylo :: ([a], [a]) -> [a]Source

qsort :: Ord a => [a] -> [a]Source

Definition of the quicksort algorithm as an hylomorphism.

bsort :: Ord a => [a] -> [a]Source

Definition of the bubble sort algorithm as an anamorphism.

isort :: Ord a => [a] -> [a]Source

Definition of the insertion sort algorithm as a catamorphism.

msplit :: [a] -> ([a], [a])Source

msort :: Ord a => [a] -> [a]Source

hsort :: Ord a => [a] -> [a]Source

Definition of the heap sort algorithm as an hylomorphism.

hsplit :: Ord a => [a] -> (a, ([a], [a]))Source

malcolm :: ((b, a) -> a) -> a -> [b] -> [a]Source

Malcolm downwards accumulations on lists.

malcolmAna :: ((b, a) -> a) -> a -> [b] -> [a]Source

Malcom downwards accumulations on lists as an anamorphism.

malcolmAna' :: ((b, a) -> a) -> ([b], a) -> [a]Source

Uncurried version of Malcom downwards accumulations on lists as an anamorphism.

Zipping

zipAna :: ([a], [b]) -> [(a, b)]Source

Definition of the zip for lists of pairs as an anamorphism.

Subsequencing

subsequences :: Eq a => [a] -> [[a]]Source

Definition of the subsequences of a list as a catamorphism.

Concatenation

cat :: ([a], [a]) -> [a]Source

Pre-defined list concatenation.

catCata :: [a] -> [a] -> [a]Source

List concatenation as a catamorphism.

type NeList a b = K a :+!: (K b :*!: I)Source

The fixpoint of the list functor with a specific terminal element.

catHylo :: ([a], [a]) -> [a]Source

List concatenation as an hylomorphism.

concat :: [[a]] -> [a]Source

Native recursive definition of lists-of-lists concatenation.

concatCata :: [[a]] -> [a]Source

Definition of lists-of-lists concatenation as an anamorphism.

merge :: Ord a => ([a], [a]) -> [a]Source

Sorted concatenation of two lists as an hylomorphism.

Summation

sumCata :: [Int] -> Int Source

Definition of inter addition as a catamorphism.

Multiplication

mult :: [Int] -> Int Source

Native recursive definition of integer multiplication.

multCata :: [Int] -> Int Source

Definition of integer multiplication as a catamorphism.

Predicates

sorted :: Ord a => [a] -> Bool Source

Edit distance

editdist :: Eq a => ([a], [a]) -> Int Source

Native recursive definition of the edit distance algorithm.

Edit distance is a classical dynamic programming algorithm that calculates a measure of distance or dierence between lists with comparable elements.

type EditDist a = K [a] :+!: ((K a :*!: K a) :*!: (I :*!: (I :*!: I)))Source

The fixpoint of the functor that represents a virtual matrix used to accumulate and look up values for the edit distance algorithm.

Since matrixes are not inductive types, a walk-through of a matrix is used, consisting in a list of values from the matrix ordered predictability.

For a more detailed explanation, please refer to http://math.ut.ee/~eugene/kabanov-vene-mpc-06.pdf.

type EditDistL a = (K [a] :*!: K [a]) :*!: (K One :+!: I)Source

editdistHylo :: Eq a => ([a], [a]) -> Int Source

The edit distance algorithm as an hylomorphism.

editDistDyna :: Eq a => ([a], [a]) -> Int Source

The edit distance algorithm as a dynamorphism.

Streams

type Stream a = K a :*!: I Source

The fixpoint of the functor of streams.

headS :: Stream a -> aSource

Stream head.

tailS :: Stream a -> Stream aSource

Stream tail.

generate :: Int -> Stream Int Source

Definition of a stream sequence generator as an anamorphism.

idStream :: Stream a -> Stream aSource

Identity o streams as an anamorphism.

mapStream :: (a -> b) -> Stream a -> Stream bSource

Mapping over streams as an anamorphism.

malcolmS :: ((b, a) -> a) -> a -> Stream b -> Stream aSource

Malcolm downwards accumulations on streams.

malcolmSAna :: ((b, a) -> a) -> a -> Stream b -> Stream aSource

Malcom downwards accumulations on streams as an anamorphism.

malcolmSAna' :: ((b, a) -> a) -> (Stream b, a) -> Stream aSource

Uncurried version of Malcom downwards accumulations on streams as an anamorphism.

inits :: Stream a -> Stream [a]Source

Promotes streams elements to streams of singleton elements.

exchFutu :: Stream a -> Stream aSource

Definition of parwise exchange on streams as a futumorphism.

Binary Tree

data Tree a Source

Datatype declaration of a binary tree.

Constructors

Empty
Node a (Tree a) (Tree a)

Instances

Show a => Show (Tree a)
Mu (Tree a)

nleaves :: Tree a -> Int Source

Counting the number of leaves in a binary tree as a catamorphism.

nnodes :: Tree a -> Int Source

Counting the number of nodes in a binary tree as a catamorphism.

genTree :: Int -> Tree Int Source

Generation of a binary tree with a specified height as an anamorphism.

preTree :: Tree a -> [a]Source

The preorder traversal on binary trees as a catamorphism.

postTree :: Tree a -> [a]Source

The postorder traversal on binary trees as a catamorphism.

Leaf Trees

data LTree a Source

Datatype declaration of a leaf tree.

Constructors

Leaf a
Branch (LTree a) (LTree a)

Instances

Mu (LTree a)

leaves :: LTree a -> [a]Source

Extract the leaves of a leaf tree as a catamorphism.

genLTree :: Int -> LTree Int Source

Generation of a leaft tree of a specified height as an anamorphism.

height :: LTree a -> Int Source

Calculate the height of a leaf tree as a catamorphism.

Rose Trees

data Rose a Source

Datatype declaration of a rose tree.

Constructors

Forest a [Rose a]

Instances

Show a => Show (Rose a)
Mu (Rose a)

preRose :: Rose a -> [a]Source

postRose :: Rose a -> [a]Source

The postorder traversal on rose trees as a catamorphism.

genRose :: Int -> Rose Int Source

Generation of a rose tree of a specified height as an anamorphism.