Generics.Pointless.Examples.Examples

Pointless Haskell: point-free programming with recursion patterns as hylomorphisms

This module provides examples, examples and more examples.

Integers

one :: One -> Int

The number 1.

Addition

add :: (Int, Int) -> Int

Pre-defined algebraic addition.

addAnaPW :: (Int, Int) -> Int

Definition of algebraic addition as an anamorphism in the point-wise style.

addAna :: (Int, Int) -> Int

Defition of algebraic addition as an anamorphism.

type From a = K a :+!: I

The fixpoint of the functor that is either a constant or defined recursively.

addHylo :: (Int, Int) -> Int

Definition of algebraic addition as an hylomorphism.

addAccum :: (Int, Int) -> Int

Definition of algebraic addition as an accumulation.

addApoPW :: (Int, Int) -> Int

addApo :: (Int, Int) -> Int

Definition of algebraic addition as an apomorphism.

Product

prod :: (Int, Int) -> Int

Pre-defined algebraic product.

prodHylo :: (Int, Int) -> Int

Definition of algebraic product as an hylomorphism

'Greater than' comparison

gt :: Ord a => (a, a) -> Bool

Pre-defined 'greater than' comparison.

gtHylo :: (Int, Int) -> Bool

Definition of 'greater than' as an hylomorphism.

Factorial

fact :: Int -> Int

Native recursive definition of the factorial function.

factPF :: Int -> Int

Recursive definition of the factorial function in the point-free style.

factPF' :: Int -> Int

Recursive definition of the factorial function in the point-free style with structural recursion.

factHylo :: Int -> Int

Definition of the factorial function as an hylomorphism.

factPara :: Int -> Int

Definition of the factorial function as a paramorphism.

factZygo :: Int -> Int

Definition of the factorial function as a zygomorphism.

Fibonnaci

fib :: Int -> Int

Native recursive definition of the fibonacci function.

fibPF :: Int -> Int

Recursive definition of the fibonacci function in the point-free style.

fibPF' :: Int -> Int

Recursive definition of the fibonacci function in the point-free style with structural recursion.

type BSTree = K One :+!: (K One :+!: (I :*!: I))

The fixpoint of the functor for a binary shape tree.

fibHylo :: Int -> Int

Definition of the fibonacci function as an hylomorphism.

fibHisto :: Int -> Int

Definition of the fibonacci function as an histomorphism.

fibDyna :: Int -> Int

Definition of the fibonacci function as a dynamorphism.

Binary Partitioning

bp :: Int -> Int

Native recursive definition for the binary partitions of a number.

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

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

bpHylo :: Int -> Int

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

bpDyna :: Int -> Int

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

Average

average :: [Int] -> Int

Recursive definition of the average of a set of integers.

averageCata :: [Int] -> Int

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

Lists

Singleton list.

wrap :: a -> [a]

Pre-defined wrapping of an element into a list.

wrapPF :: a -> [a]

Definition of wrapping in the point-free style.

Tail

tail :: [a] -> [a]

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

tailPF :: [a] -> [a]

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

tailCata :: [a] -> [a]

Definition of the tail of a list as an anamorphism.

tailPara :: [a] -> [a]

Definition of the tail of a list as a paramorphism.

Length

length :: [a] -> Int

Native recursion definition of list length.

lengthPF :: [a] -> Int

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

lengthPF' :: [a] -> Int

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

lengthHylo :: [a] -> Int

Definition of list length as an hylomorphism.

lengthAna :: [a] -> Int

Definition of list length as an anamorphism.

lengthCata :: [a] -> Int

Definition of list length as a catamorphism.

Filtering

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

Native recursive definition of list filtering.

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

Definition of list filtering as an catamorphism.

Generation

repeatAna :: a -> [a]

Generation of infinite lists as an anamorphism.

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

Finite replication of an element as an anamorphism.

downtoAna :: Int -> [Int]

Generation of a downwards list as an anamorphism.

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

Ordered list insertion as an apomorphism.

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

Ordered list insertion as a paramorphism.

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

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

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

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

Extraction

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

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

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

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

Partition

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

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

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

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

Transformations

isum :: [Int] -> [Int]

Incremental summation as a catamorphism.

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

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

data Some a

Constructors

Wrap a

Insert a (Some a)

Instances

Eq a => Eq (Some a)

Show a => Show (Some a)

Mu (Some a)

type PF (Some a) = (:+:) (Const a) ((:*:) (Const a) Id)

neCons :: (a, Some a) -> Some a

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

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

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

Definition of list mapping as a catamorphism.

reverseCata :: [a] -> [a]

Definition of list reversion as a catamorphism.

reverseAccum :: [a] -> [a]

Linear version of reverse using accumulations

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

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

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

Definition of the quicksort algorithm as an hylomorphism.

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

Definition of the bubble sort algorithm as an anamorphism.

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

Definition of the insertion sort algorithm as a catamorphism.

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

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

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

Definition of the heap sort algorithm as an hylomorphism.

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

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

Malcolm downwards accumulations on lists.

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

Malcom downwards accumulations on lists as an anamorphism.

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

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

Zipping

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

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

Subsequencing

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

Definition of the subsequences of a list as a catamorphism.

Concatenation

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

Pre-defined list concatenation.

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

List concatenation as a catamorphism.

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

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

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

List concatenation as an hylomorphism.

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

Native recursive definition of lists-of-lists concatenation.

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

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

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

Sorted concatenation of two lists as an hylomorphism.

Summation

sumCata :: [Int] -> Int

Definition of integerr addition as a catamorphism.

sumAccum :: ([Int], Int) -> Int

Definition of integerr addition as an accumulation.

Multiplication

mult :: [Int] -> Int

Native recursive definition of integer multiplication.

multCata :: [Int] -> Int

Definition of integer multiplication as a catamorphism.

Predicates

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

Edit distance

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

Native recursive definition of the edit distance algorithm.

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

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

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)

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

The edit distance algorithm as an hylomorphism.

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

The edit distance algorithm as a dynamorphism.

Streams

type Stream a = K a :*!: I

The fixpoint of the functor of streams.

headS :: Stream a -> a

Stream head.

tailS :: Stream a -> Stream a

Stream tail.

generate :: Int -> Stream Int

Definition of a stream sequence generator as an anamorphism.

idStream :: Stream a -> Stream a

Identity o streams as an anamorphism.

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

Mapping over streams as an anamorphism.

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

Malcolm downwards accumulations on streams.

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

Malcom downwards accumulations on streams as an anamorphism.

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

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

inits :: Stream a -> Stream [a]

Promotes streams elements to streams of singleton elements.

exchFutu :: Stream a -> Stream a

Definition of parwise exchange on streams as a futumorphism.

Binary Tree

data Tree a

Datatype declaration of a binary tree.

Constructors

Empty

Node a (Tree a) (Tree a)

Instances

Show a => Show (Tree a)

Mu (Tree a)

type PF (Tree a) = (:+:) (Const One) ((:*:) (Const a) ((:*:) Id Id))

The functor of a binary tree.

nleaves :: Tree a -> Int

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

nnodes :: Tree a -> Int

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

genTree :: Int -> Tree Int

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

preTree :: Tree a -> [a]

The preorder traversal on binary trees as a catamorphism.

postTree :: Tree a -> [a]

The postorder traversal on binary trees as a catamorphism.

Leaf Trees

data LTree a

Datatype declaration of a leaf tree.

Constructors

Leaf a

Branch (LTree a) (LTree a)

Instances

Eq a => Eq (LTree a)

Show a => Show (LTree a)

Mu (LTree a)

type PF (LTree a) = (:+:) (Const a) ((:*:) Id Id)

The functor of a leaf tree.

leaves :: LTree a -> [a]

Extract the leaves of a leaf tree as a catamorphism.

genLTree :: Int -> LTree Int

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

height :: LTree a -> Int

Calculate the height of a leaf tree as a catamorphism.

Rose Trees

data Rose a

Datatype declaration of a rose tree.

Constructors

Forest a [Rose a]

Instances

Show a => Show (Rose a)

Mu (Rose a)

type PF (Rose a) = (:*:) (Const a) ((:@:) [] Id)

The functor of a rose tree.

preRose :: Rose a -> [a]

postRose :: Rose a -> [a]

The postorder traversal on rose trees as a catamorphism.

genRose :: Int -> Rose Int

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