Categories
Uncategorized

My solutions of challenges in book “Category Theory for Programmers”

Chapter 1

1.1) Implement, as best as you can, the identity function in your favorite language (or the second favorite, if your favorite language happens to be Haskell).

function identity(x) {
    return x;
}

If we would like to be more type-strict, we could use TS.

function identity<T>(x: T) {
    return x;
}

1.2) Implement the composition function in your favorite language. It takes two functions as arguments and returns a function that is their composition.

function composition<T1 extends any[], T2, T3>(
    f: (p: T2) => T3, 
    g: (...p: T1) => T2
) {
    return function (...p: T1) {
        return f(g(...p));
    }
}

function add(a: number, b: number) {
    return a + b;
}

function mul100(x: number) {
    return x * 100;
}

const f = composition(mul100, add);

console.log(f(10, 30)); // prints 4000

1.3) Write a program that tries to test that your composition function respects identity.

function lIdentity<A extends any[], B> (g: (...x: A) => B){
    return function (...x: A) {
        return composition(identity, g)(...x);
    }
}

function rIdentity<A, B>(f: (x: A) => B) {
    return function (x: A) {
        return composition(f, identity)(x);
    }
}

const f1 = rIdentity(mul100);
const f2 = lIdentity(mul100);

console.log(f1(100) === f2(100)); // true
console.log(f1(0) === f2(0)); // true
console.log(f1(0) !== f2(10)); // true

// ...

1.4) Is the world-wide web a category in any sense? Are links morphisms?

No. The transitive property is not always fulfiled.

We can definitely find pages, where:

– Link from page A points to page B.
– Link from page B points to page C.
– There is no link from A to C – thus transitive property is not fulfiled.

1.5) Is Facebook a category, with people as objects and friendships as morphisms?

No. Because of same reason as in 1.4.

1.6) When is a directed graph a category?

When for every directed path {(A,B), (B, C)} (where A, B, C are nodes of graph) exists edge (A, C). And for every node V exists edge (V, V).

2.1) Define a higher-order function (or a function object) memoize in your favorite language. This function takes a pure function f as an argument and returns a function that behaves almost exactly like f, except that it only calls the original function once for every argument, stores the result internally, and subsequently returns this stored result every time it’s called with the same argument. You can tell the memoized function from the original by watching its performance. For instance, try to memoize a function that takes a long time to evaluate. You’ll have to wait for the result the first time you call it, but on subsequent calls, with the same argument, you should get the result immediately.


function memo <A extends any[], B>(f: (...x: A) => B) {
    const memory: Record<string, B> = {};
    
    return function(...x: A): B {
        const key = JSON.stringify(x);
        if(memory[key]) {
            return memory[key];
        }

        memory[key] = f(...x);

        return memory[key];
    }
}

function getRunTime<A extends any[], B>(f: (...x: A) => B, ...params: A): Number {
    const start = new Date().getTime();
    f(...params);
    const stop = new Date().getTime();

    return stop - start;
}

function takeLong(returnValue: Number) {
    for(let i = 0; i<1000000000; i++) {}
    return returnValue;
}

console.log(getRunTime(takeLong, 1)); // 750
console.log(getRunTime(takeLong, 1)); // 757
console.log(getRunTime(takeLong, 2)); // 636

const memoizedTakeLong = memo(takeLong);

console.log(getRunTime(memoizedTakeLong, 1)); // 676
console.log(getRunTime(memoizedTakeLong, 1)); // 0
console.log(getRunTime(memoizedTakeLong, 2)); // 644

2.2) Try to memoize a function from your standard library that you normally use to produce random numbers. Does it work?

No, because random() function is not pure. Memoization would cause the memoized random function to return same value as when it was called for first time.

2.3) Most random number generators can be initialized with a seed. Implement a function that takes a seed, calls the random number generator with that seed, and returns the result. Memoize that function. Does it work?

// 32-bit random number generator getter
function getRandomGenerator(seed: number) {
    let x = seed;
    let a = 69069;
    let c = 1;

    return function random() {
        x = (x * a + c) % Math.pow(2, 32);
        return x;
    }
}

const random = getRandomGenerator(100);
console.log(random()); // 6906901
console.log(random()); // 311375314
console.log(random()); // 1480311595
console.log(random()); // 1945073776

function runWithSeed(seed: number) {
    const random = getRandomGenerator(seed);

    return random();
}

console.log(runWithSeed(100)); // 6906901
console.log(runWithSeed(100)); // 6906901
console.log(runWithSeed(100)); // 6906901
console.log(runWithSeed(100)); // 6906901

Code snippet above demonstrates solution for this challenge using one of the most simple random number generators – linear congruent generator.

If result of random() call would depend on something outside getRandomGenerator scope (such as time etc.), it wouldn’t be possible to memoize runWithSeed function.

2.4) Which of these C++ functions are pure? Try to memoize them and observe what happens when you call them multiple times: memoized and not.

  1. Factorial – pure
  2. std::getchar() – impure (depends on stdin)
  3. f() – is impure – memoizing would cause print to stdout only on first call
  4. f(int x) – is impure – result depends on static int y;, which is stored outside of scope and updated each call

2.5) How many different functions are there from Bool to Bool? Can you implement them all?

Four.

fxfx(true)fx(false)DefinitionFuncition name
f1 truetruef1(x) = trueT
f2truefalsef2(x) = xidentity
f3falsetruef3(x) = ¬xnegation
f4falsefalsef4(x) = falseF

2.6) Draw a picture of a category whose only objects are the types Void, () (unit), and Bool; with arrows corresponding to all possible functions between these types. Label the arrows with the names of the functions.

To VoidTo UnitTo Bool
From Voididentity: Void -> Voidabsurd: Void -> ()absurd: Void -> Bool
From Unitidentity: Unit -> Unitfx: Unit -> Bool
(f1() = true, f2() = false)
From Boolunit: Bool -> ()
(unit (x) = ())
identity: Bool -> Bool
(T(x)=true, id(x)=x, neg(x)=¬x, F(x)=false)
Categories
Uncategorized

My (random) thoughts on “Category Theory for Programmers”

I have been interested in programming for a while and functional programming especially. In order to improve my theoretical background, I have started reading book “Category Theory for Programmers” (PDF and sources here). In this article I would like to present some of my thoughts and answers to the questions in chapeters of these books.

You can see my solutions of challenges from book in my post My solutions of challenges in book „Category Theory for Programmers“.

Chapter 1

  • Category theory is a tool for categorising mathematical objects
  • “arrow” between objects in category theory is called morphism
  • composition is binary operation for composing objects
    • this operation is associative
    • and has unit

Composition:

    \begin{align*}  f: A \rightarrow B \\ g: B \rightarrow C \\ g \circ f: A \rightarrow C\\ \end{align*}

Asociativity (f, g, h are functions):

    \begin{align*}  f \circ (g \circ h) = (f \circ g) \circ h = f \circ g \circ h \end{align*}

Unit:

    \begin{align*}  \forall\ A\ \exists\ id_A&: \\ &id_A \circ f = f \\ &f \circ id_A = f \end{align*}

  • for every objects A, B, C from category theory, where f is morphism from A to B and g is morphism from B to C has to exist morphism g ○ f (from A to C)

Chapter 2

  • type are intuitively sets of values (kind of) – they can be finite or infinite too (Bool vs Integer)
  • mathematical function is relation between two values, it doesn’t describe steps to produce output from input

So the question is, do we want to make monkeys happy, or do we want to produce correct programs?

  • example types in Haskell
    • Void – empty set
      • function with Void cannot be called. There is no way to provide no value
    • Unit – set with one value – empty tupple ()
      • can be used as parameter for constant function
    • Bool – set with two values (True and False)
absurd :: Void -> a

f44 :: () -> Integer
f44 () = 44

fInt :: Integer -> ()
fInt _ = ()

data Bool = True | False

Chapter 3

  • categories examples
    • empty – without objects and morphisms
    • from graph
      • begin with directed graph
      • add identity morphism for each node
      • for each pair of edges (A, B) and (B, C), add (A, C)
      • repeat last step until no morphism can be added
      • thus we are creating category with object for every node of graph and morphism for every directed path
      • a category made from graph using these steps is called free category
    • orders
      • morphism in order is ≥ (relation between objects)
      • hom-set set of morphisms from a to b – C(a, b)
      • types
        • preorder – set with ≥ relation
          • at most one morphism from object a to object b = thin category
          • |C(a, b)| is 0 or 1
          • can contain cycle
        • partial order – if a ≥ b and b ≥ a, then a = b
          • can’t contain cycle
        • linear/total order – relation ≥ is defined for every pair of elements from set
      • common sorting algorithms can be used only on total order
      • partial order can be sorted using topological sort
    • monoids
      • monoid is set with binary operation
      • this operation is asociative and has unit
      • it doesn’t have to be commutative

    \begin{align*} &(S, \circ) \\ S & \textrm{ ... is set } \\ \circ & \textrm{ ... is binary operation} \\ \\ \forall a, b \in S: a \circ b \in S & \textrm{ ... operation is closed} \\ \exists u \in S \forall a \in S: a \circ x = x \circ a = a & \textrm{ ... has unit element} \\ \forall a, b, c \in S: (a \circ b) \circ c = a \circ (b \circ c) = a \circ b \circ c & \textrm{ ... operation is associative} \end{align*}