Generalised fixed point for any functor f. Note that unFix (Fix x) == x

List Functor where r is the carrier type.

Natural numbers Functor.

Natural numbers type.

The code defines a type synonym RAlgebra that represents a recursive algebra for a functor f. An R-algebra is a function that takes a fixed point of a functor Fix f and a value of type f a, and returns a value of type a.

The Fix type is used to define recursive data structures in Haskell. It is a type constructor that takes a functor f as an argument and returns a fixed point of f. The Fix type is used to define recursive data structures by wrapping a value of type f (Fix f) in a Fix constructor.

The RAlgebra type synonym is used to define a function that takes a fixed point of a functor Fix f and a value of type f a, and returns a value of type a. This function is used to define recursive functions that operate on data structures defined using Fix.

The RAlgebra type synonym is a higher-order type that takes two type arguments: f, which is a functor, and a, which is the return type of the algebra. The RAlgebra type synonym is used to define recursive functions that operate on data structures defined using Fix.

Anamorphism - produce a structure.

Catamorphism - consume a structure.

Paramorphism - improved consumption of a structure.

Paramorphism where input list is the first parameter. This comes from Making Sense of Recursion Patterns by Paul Bailes and Leighton Brough. It extends foldr by supplying to the combining operation (op) the unprocessed list tail, in addition to the head and the result of recursion on the tail as provided by foldr.

Sum a list:

>>> para' (const . (+)) 0 [1,2,3]
6

Suffixes of a list:

>>> para' (const (:)) [] "abcd"
["bcd","cd","d",""]

Paramorphism using foldr. This comes from Making Sense of Recursion Patterns by Paul Bailes and Leighton Brough.

The following shows how to get a catamorphism from a paramorphism. In this example, we are calculating the sum of items from a list.

Sum a list:

>>> para'' (const . (+)) 0 [1,2,3]
6

Suffixes of a list:

>>> para'' (\ _ xs xss -> xs : xss) [] "abcd"
["bcd","cd","d",""]

>>> para'' (const (:)) [] "abcd"
["bcd","cd","d",""]

Feed coalgebra to anamorphism. This will build a list.

>>> buildListF 4 :: Fix (ListF Int)
ConsF 4 (ConsF 3 (ConsF 2 (ConsF 1 NilF)))

Coalgebra is a non-recursive function to generate a ListF entry.

An alegbra over ListF to get list length.

Length is a folding operation, i.e. a Catamorphism.

>>> (lengthListF . buildListF) 4
4

Length using special case of paramorphism.

>>> lengthListF' (buildListF 4)
4

Convert Natural number to an integer.

>>> fromNat (toNat 4)
4

Build a natural number from an interger.

>>> toNat 4
SuccF (SuccF (SuccF (SuccF ZeroF)))

Insert element into list at correct ordered position using foldr.

>>> insert 1 [2,3,4]
[1,2,3,4]

>>> insert 'c' "abde"
"abcde"

>>> insert 'f' "abcde"
"abcdef"

>>> insert 'o' "oa"
"ooa"

Insert element into list at correct ordered position.

>>> insert' 1 [2,3,4]
[1,2,3,4]

>>> insert' 1 []
[1]

>>> insert' 'c' "abde"
"abcde"

>>> insert' 'c' "abde" == "abcde"
True

>>> insert' 'o' "oa"
"ooa"

Convert a ListF to a standard list.

Indexing a list.

>>> idx0 "abcde"
[0,1,2,3,4]

Alternate list indexing using foldr.

>>> idx1 "abcde"
[0,1,2,3,4]

Alternate list indexing using zipWith.

>>> idx2 "abcde"
[0,1,2,3,4]

List indexing using foldr.

>>> idx3 "abcde"
[0,1,2,3,4]

List indexing using foldr with parameter last.

>>> idx4 "abcde"
[0,1,2,3,4]