Category Theory for Programmers: Exercises (Chapter 7)

Functors

1. Can we turn the Maybe type constructor into a functor by defining:

fmap _ _ = Nothing

which ignores both of its arguments?

It does not preserve identity:

  fmap id Nothing
= { definition of fmap }
  Nothing
= { definition of id }
  id Nothing

  fmap id (Just x)
= { definition of fmap }
  Nothing
!= { definition of id }
  id (Just x)

And it does not preserve composition since the last expression evaluates to fmap g Nothing and not fmap g (Just x):

  fmap (g . f) Nothing
= { definition of fmap }
  Nothing
= { definition of fmap }
  fmap g Nothing
= { definition of fmap }
  fmap g (fmap f Nothing)

  fmap (g . f) (Just x)
= { definition of fmap }
  Nothing
= { definition of fmap }
  fmap g (Just x)
!= { definition of fmap }
  fmap g (fmap f (Just x))

2. Prove the functor laws for the reader functor:

fmap f g = f . g

Preserves identity:

  fmap id g
= { definition of fmap }
  id . g
= { definition of fmap }
  g
= { definition of id }
  id g

Preserves composition:

  fmap (g . f) h
= { definition of fmap }
  (g . f) . h
= { definition of fmap }
  g . (f . h)
= { definition of fmap }
  fmap g (f . h)
= { definition of fmap }
  fmap g (fmap f h)
= { definition of fmap }
  (fmap g . fmap f) h

3. Implement the Reader functor in a language other than Haskell.

interface Functor<A, B, FA, FB> {
    fmap: (f: (a: A) => B) => (fa: FA) => FB
}

interface IReader<A, B, R> extends Functor<A, B, (r: R) => A, (r: R) => B> {}

class Reader<A, B, R> implements IReader<A, B, R> {
    fmap(f: (a: A) => B) {
        return (g: (r: R) => A) => (r: R) => f(g(r))
    }
}

const strReader = new Reader<number, boolean, string>

const isEvenLength = strReader.fmap((n) => !(n % 2))((s) => s.length)

isEvenLength('hello') // false
isEvenLength('world!') // true

4. Prove the functor laws for the list functor. Assume that the laws are true for the tail part of the list you’re applying it to.

Preserves identity:

  fmap id (Cons x Nil) 
= { definition of fmap }
  Cons (id x) (fmap id Nil)
= { definition of fmap }
  Cons x Nil
= { definition of id }
  id (Cons x Nil)

Preserves composition:

  fmap (g . f) (Cons x Nil)
= { definition of fmap }
  Cons ((g . f) x) (fmap (g . f) Nil)
= { definition of fmap }
  Cons ((g . f) x) Nil
= { definition of fmap }
  Cons (g (f x)) Nil
= { definition of fmap }
  fmap g (Cons (f x) Nil)
= { definition of fmap }
  fmap g (fmap f (Cons x Nil))
= { definition of fmap }
  (fmap g . fmap f) (Cons x Nil)