Exercises on catamorphisms

[benediktahrens]

Exercises suggested by @arnoudvanderleer - thanks a lot!

An exercise about representing functions as catamorphisms (or rewriting functions using fold):

• We can represent numbers as big-endian binary numbers, in the set List({0, 1}): the lists with elements in the set {0, 1}. (For example, 13 becomes 1101, which becomes (cons 1 (cons 1 (cons 0 (cons 1 nil))))). Show that we can give the function bin2int: List({0, 1}) -> N, that converts big-endian binary representations to positive integers, as a catamorphism. For example, (bin2int (cons 1 (cons 0 nil))) = 2 and (bin2int (cons 1 (cons 1 (cons 0 (cons 1 nil))))) = 13). i.e. with F the functor for which List({0, 1}) is an initial algebra, show that there exists an F-algebra (N, f) such that (| f |) = bin2int.
• We can also represent a number as a little-endian binary number. Then 13 becomes 1011, which becomes (cons 1 (cons 0 (cons 1 (cons 1 nil))))). Why can't we represent the function bin2int2: List({0, 1}) -> N, that converts little-endian binary representations back to positive integers, as a catamorphism?
• Show that there exists an F-algebra (N x N, f) such that pr1 ∘ (| f |) is our function bin2int2, for (| f |) the catamorphism induced by f, and with pr1 the projection on the first coordinate. I.e. show that there exists some function g: List({0, 1}) -> N x N that is a catamorphism, and when restricted to the first coordinate gives our function bin2int2.