Category Theory for Programmers: Exercises (Chapter 6)

Simple Algebraic Data Types

1. Show the isomorphism between Maybe a and Either () a.

maybeToEither :: Maybe a -> Either () a
maybeToEither Nothing = Left ()
maybeToEither (Just a) = Right a

eitherToMaybe :: Either () a -> Maybe a
eitherToMaybe (Left ()) = Nothing
eitherToMaybe (Right a) = Just a

2. Here’s a sum type defined in Haskell:

data Shape = Circle Float | Rect Float Float

When we want to define a function like area that acts on a Shape, we do it by pattern matching on the two contructors:

area :: Shape -> Float
area (Circle r) = pi * r * r
area (Rect d h) = d * h

Implement Shape in C++ or Java TypeScript as an interface and create two classes: Circle and Rect. Implement area as a virtual function.

interface Shape {
    area: () => number;
}

class Circle implements Shape {
    r: number;

    constructor(r: number) {
        this.r = r;
    }

    area() {
        return (Math.PI * this.r) ^ 2;
    }
}

class Rect implements Shape {
    d: number;
    h: number;

    constructor(d: number, h: number) {
        this.d = d;
        this.h = h;
    }

    area() {
        return this.d * this.h;
    }
}

3. Continuing with the previous example: We can easily add a new function circ that calculates the circumference of a Shape. We can do it without touching the definition of Shape:

circ :: Shape -> Float
circ (Circle r) = 2.0 * pi * r
circ (Rect d h) = 2.0 * (d + h)

Add circ to your C++ or Java TypeScript implementation. What parts of the original code did you have to touch?

It’s the same amount of work to do this in TypeScript and you don’t strictly need to add circ to the Shape interface.

interface Shape {
    area: () => number;
    circ: () => number;
}

class Circle implements Shape {
    // ...
    circ() {
        return 2 * Math.PI * this.r;
    }
}

class Rect implements Shape {
    // ...
    circ() {
        return 2 * this.d + this.h;
    }
}

4. Continuing further: Add a new shape, Square, to Shape and make all the necessary updates. What code did you have to touch in Haskell vs C++ or Java TypeScript?

Changes to the Haskell code:

data Shape = Circle Float
           | Rect Float Float
           | Square Float Float

area :: Shape -> Float
-- ...
area (Square d h) = d * h

circ :: Shape -> Float
-- ...
circ (Square d h) = 2.0 * (d + h)

Adding Square to the Haskell code is more work than in TypeScript where inheritance can be used (considering that a square is a special case of a rectangle):

class Square extends Rect {}

5. Show that a + a = 2 * a holds for types (up to isomorphism). Remember that 2 corresponds to Bool.

{-
  a + a = 2 * a translates to types as:
  Either a a = (Bool, a) 
-}

-- To convert the sum to the product we can place the value
-- as the second element of the pair and for the first element
-- choose True or False for Left and Right respectively.
sumToProd :: Either a a -> (Bool, a)
sumToProd e = 
    case e of
        Left x -> (True, x)
        Right x -> (False, x)

-- To convert the product to the sum we can return Left a or
-- Right a depending on whether the Bool value is True or False.
prodToSum :: (Bool, a) -> Either a a
prodToSum (x, y) = 
    case x of
        True -> Left y
        False -> Right y