Category Theory For Programmers Chapter 1

Chapter1.java

package eu.javaland.fpworkshop.categorytheory;

import static org.assertj.core.api.Assertions.assertThat;

import java.util.function.Function;

import net.jqwik.api.ForAll;
import net.jqwik.api.Property;


public class Chapter1 {
    
    @Property
    public void compositionShouldRespectIdentity(@ForAll String input) {
        Function<String, String> otherFunction = in -> in+"composed";
        assertThat(compose(otherFunction, identity()).apply(input)).isEqualTo(compose(identity(), otherFunction).apply(input));
    }

    <A> Function<A, A> identity() {
        return a -> a;
    }

    <A,B,C> Function<A,C> compose(Function<? super A, ? extends B> before, Function<B,C> after) {
        return a -> after.apply(before.apply(a));
    }

    // Is the world wide web a morphism? Are links morphisms?
    // Under the assumption that the objects are resources and morphisms are hyper links, then the world-wide web is not a category.
    // There are resources which don't have an identity. That is, these resources do not have a hyper link pointing to themselves.
    // Taking the jumps of the random surfer model into account (see PageRank), then the world wide web is a category because these
    // random jumps could lead to the same resource again.

    // Is Facebook a category, with people as objects and friendships as morphisms?
    // No. Friendships do not compose. Person A being friends with person B does not imply a friendship between person A and Person C 
    // when Person B is friends with Person C.

    // When is a directed graph a category?
    // Objects = Nodes, Morphisms = Edges
    // Only when for every node there is an edge to itself.
    
}

Chapter2.java

package eu.javaland.fpworkshop.categorytheory;

import io.vavr.Tuple;
import io.vavr.Tuple2;
import io.vavr.collection.Stream;
import net.jqwik.api.Example;
import net.jqwik.api.ForAll;
import net.jqwik.api.Property;
import net.jqwik.api.constraints.IntRange;

import java.util.List;
import java.util.Random;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.Function;
import java.util.stream.IntStream;

import static org.assertj.core.api.Assertions.assertThat;

public class Chapter2 {

    // Chapter notes
    // I was a bit confused by this chapter. I did not know the difference between types with no value and types with
    // exactly one value. Kotlin and Scala call the former type Nothing (see also:
    // https://medium.com/thoughts-overflow/kotlin-has-nothing-but-there-is-nothing-like-nothing-in-java-cab98e4f4d26).
    // There is no such type in Java. In Java, the Void type in combination with the null value has the properties of a
    // Unit type (see: https://en.wikipedia.org/wiki/Unit_type). Such a function is pure, if it always returns the
    // same value.
    // I don't think inline types will bring a nothing type, because an inlined type will always have a default value.

    @Property
    public void pureFunctionWithUnitParameterWillAlwaysBeTheSame(){
        Function<Void, Integer> f44 = parameter -> 44;

        assertThat(f44.apply(null)).isEqualTo(44);
    }

    @Property // Unit: Type = Void, value = null
    public void pureFunctionWithUnitReturnTypeWillAlwaysBeNull(@ForAll Integer input){
        Function<Integer, Void> fint = parameter -> null;

        assertThat(fint.apply(input)).isEqualTo(null);
    }

    @Property // Unit: Type = Unit, value = null
    public void polymorphicUnitFunctionMapsAllValuesToNull(@ForAll String stringInput, @ForAll Integer intInput){
        assertThat(unit().apply(stringInput)).isEqualTo(unit().apply(intInput));
    }

    // We can define a unit type, too.
    // Type = Unit, value = null
    enum Unit {}

    private <A> Function<A, Unit> unit() {
        return __ -> null;
    }

    // As any reference type in Java can be null, we assume that null = false in case of Bool. Otherwise, we would
    // have to deal with a trinary boolean logic. However, primitive types cannot be null. boolean is can only be false
    // or true.
    enum Bool {
        TRUE
    }

    @Property
    public void memoizeShouldAlwaysReturnTheSameResultAsTheFirstOrderFunction(@ForAll List<String> input){
        Function<String, String> firstOrderFunction = Function.identity();

        input.forEach(in ->
                assertThat(memoize(firstOrderFunction).apply(in)).isEqualTo(firstOrderFunction.apply(in)).isEqualTo(in)
        );

    }

    @Example
    public void randomNumbersAreNotGoodForMemoization() {
        Function<Random, Integer> nextIntMemoized = memoize(Random::nextInt);
        var seed = 1000;
        var random = new Random(seed);

        // In Java, each class instance has an own identity. This means, we always pass the same instance to the
        // nextIntMemoized function. As this value is memoized, there will only ever be one value generated by the
        // random number generator. This also means, that Random::nextInt is not pure because for the same argument
        // different numbers are generated.
        IntStream.range(0, 100)
                .map(__ -> nextIntMemoized.apply(random))
                .forEach(number -> assertThat(number).isEqualTo(-1244746321));

        // To make this pure, we should return the generated value and a new random number generator
        Function<Random, Tuple2<Integer, Random>> nextInWithRng = rng -> {
            int nextInt = rng.nextInt();
            return Tuple.of(nextInt, new Random());
        };
        var nextIntMemoizedWithRng = memoize(nextInWithRng);

        // Let's reduce this
        var numbersAndRandom = Stream.fill(100, nextIntMemoizedWithRng).foldLeft(Tuple.of(io.vavr.collection.List.<Integer>of(), new Random()), (acc, f) -> {
            var next = f.apply(acc._2);
            return Tuple.of(acc._1.append(next._1), next._2);
        });

        // Memoization has no effect, because a new instance of Random is generated after every call which returns
        // a random number. Providing a seed causes the random number generator to produce the same number again.

        Function<Integer, Integer> nextInt = memoize(s -> {
            try {
                Thread.sleep(100);
                System.out.println("Seed: "+s);
                return new Random(s).nextInt();
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
        });

        var firstRun = Stream.range(0, 50).map(nextInt).foldLeft(io.vavr.collection.List.empty(), io.vavr.collection.List::append);
        var secondRun = Stream.range(0, 50).map(nextInt).foldLeft(io.vavr.collection.List.empty(), io.vavr.collection.List::append);

        assertThat(firstRun).isEqualTo(secondRun);

    }

    @Example
    public void whichFunctionsArePure(){
        // This is Java and not C++, but the factorial function can be written here, too.
        // For the same input we always get the same result. Apart from the returning the number there is no other
        // effect. Seen from the call-site fact is pure. And this is what I care to observe.
        Function<Integer, Integer> memoizedFact = memoize(this::fact);
        Stream.continually(15).take(5).map(memoizedFact::apply).forEach(System.out::println);

        // std::getchar is not pure. It takes unit, but can return different values for different calls.

        // Function f is not pure. The effect of writing to stdout is not part of the return value. This means, writing
        // to stdout is a side effect. In other words, function f breaks referential transparency (see:
        // https://wiki.haskell.org/Referential_transparency): The returned value does not have same meaning in the
        // context of this program. It misses writing to stdout. This can be seen when using the memoized function.
        Function<Integer, Boolean> memoizedF = memoize(this::f);
        Stream.continually(1).take(5).map(memoizedF).forEach(System.out::println);
    }

    @Property
    public void callingAPureFunctionWithTheSameValueMultipleTimesShouldYieldTheSameResult(@ForAll @IntRange(max = 10) int number){
        // Function otherF is not pure.
        Function<Integer, Integer> otherMemoized = memoize(this::otherF);
        assertThat(otherF(number)).isEqualTo(otherMemoized.apply(number));

    }

    int fact(int n){
        int i;
        int result = 1;
        for(i = 2; i <= n; ++i){
            result *= i;
        }
        return result;
    }

    boolean f(int x) {
        System.out.println("Hello !");
        return true;
    }

    static int y = 0;
    int otherF(int x){
        y += x;
        return y;
    }

    private <A,B> Function<A, B> memoize(Function<A,B> firstOrderFunction) {
        if(firstOrderFunction instanceof Memoized){
            return firstOrderFunction;
        }
        var cache = new ConcurrentHashMap<A, B>();
        return (Function<A, B> & Memoized) a -> cache.computeIfAbsent(a, firstOrderFunction);
    }

    // Let's steal the idea from vavr to use Memoized as marker interface.
    interface Memoized {}


    // How many functions are there from Bool to Bool? Can you implement them all?

    @Example
    public void fromBoolToBool(){
        // I was under the impression that there were just two: not and id. According to the answer on
        // StackOverflow (https://stackoverflow.com/questions/63863605/how-many-different-functions-are-there-from-bool-to-bool),
        // there are four:
        // * Map all values from domain bool to false: f -> f, t -> f
        // * Map all values to themselves: f -> f, t -> t
        // * Map all values to the other value: f -> t, t -> f
        // * Map all values to true: f -> t, t -> t
        Function<Boolean, Boolean> constantTrue = __ -> true;
        Function<Boolean, Boolean> id = x -> x;
        Function<Boolean, Boolean> not = x -> !x;
        Function<Boolean, Boolean> constantFalse = __ -> false;
    }


// Draw category with functions
/*
 *                                           unit
 *            absurd                       ┌──────┐
 *          ┌───────┐                      │      │
 *          │       ▼                      │      │
 *          │   ┌────────┐           ┌─────┴──┐   │
 *          │   │        │  absurd   │        │   │
 *          └───┤  Void  ├──────────►│   ()   │◄──┘
 *              │        │           │        │
 *              └───┬────┘          ┌┴──┬─────┘
 *           absurd │      true     │   │   ▲
 *                  │  ┌────────────┘   │   │
 *  constantTrue    ▼  ▼                │   │
 *    ┌─────────┬────────┐              │   │
      │         │        │   false      │   │
 *    └───────► │        │◄─────────────┘   │
 * constantFalse│  Bool  │                  │
 *    ┌─────────┤        ├──────────────────┘
 *    └───────► ├────┬───┘       unit
 *              │ ▲  │ ▲
 *              │ │  │ │
 *              │ │  │ │
 *              └─┘  └─┘
 *              not   id
 */

}