Category Theory for Programmers Challenges
Glossary:
 Category
 Category of sets
 A category with sets as objects and total functions as morphisms.
 Cocone
 A natural transformation.
 Colimit
 A universal cone.
 Cone
 A natural transformation.
 Cospan
 A diagram of shape 1 → 2 ← 3.
 Diagram
 A functor.
 Equalizer
 A limit.
 Free monoid
 The monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element.
 Functor
 Homomorphism
 Kleisli category
 Limit
 A universal cone.
 Monoid
 An object M together with two morphisms
 μ: M ⊗ M → M called multiplication,
 η: I → M called unit.
 An object M together with two morphisms
 Monoidal category
 A category C equipped with a bifunctor ⊗: C × C → C that is associative up to a natural isomorphism, and an object I that is both a left and right identity for ⊗, again up to a natural isomorphism.
 Natural transformation
 A family of morphisms.
 Presheaf
 A contravariant functor from any category to the category of sets.
 Product category
 Pullback
 A limit of a cospan.
 Pushout
 A colimit of a span.
 Representable functor
 Span
 A diagram of shape 1 ← 2 → 3.
Part One
1 Category: The Essence of Composition
1.4 Challenges
1.4  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).
See here.
1.4  2
Implement the composition function in your favorite language. It takes two functions as arguments and returns a function that is their composition.
See here.
1.4  3
Write a program that tries to test that your composition function respects identity.
See here.
1.4  4
Is the worldwide web a category in any sense? Are links morphisms?
The worldwide web is a category if we consider reachability relations as morphisms. Links are not morphisms because they can not be composited. Having a link from a to b and b to c, does not mean there is a link from a to c.
1.4  5
Is Facebook a category, with people as objects and friendships as morphisms?
 Skipped.
1.4  6
When is a directed graph a category?
When its transitive closure is it self.
2 Types and Functions
2.7 Challenges
2.7  1
Define a higherorder function (or a function object)
memoize
in your favorite language. This function takes a pure functionf
as an argument and returns a function that behaves almost exactly likef
, 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.
See here.
2.7  2
Try to memoize a function from your standard library that you normally use to produce random numbers. Does it work?
No, it does not work. A function for generating random numbers needs to be able to generate different numbers for different calls, which means it is not pure. Memoizing it will cause the first generated number being remembered, then the subsequent calls will always return the same number, which changes the intended behavior.
2.7  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?
Yes it works. The output of the function is entirely determined by the seed, so it is a pure function, which means memoizing will work.
2.7  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.
 The factorial function from the example in the text.
std::getchar()
bool
int
 Pure.
 Not pure, because different values could be returned depends on user input.
 Not pure, because it has a side effect of printing texts.
 Not pure, because the global variable
y
is accessed, which may cause the return value to be different even if the argumentx
is the same. For example, callf
twice with1
, the first timef
will return1
, and the second timef
will return2
.
2.7  5
How many different functions are there from
Bool
toBool
? Can you implement them all?
There are 4 different pure functions. See here.
2.7  6
Draw a picture of a category whose only objects are the types
Void
,()
(unit), andBool
; with arrows corresponding to all possible functions between these types. Label the arrows with the names of the functions.
The graph is too complex to draw, so here are the edges described in text.
Void
→()
:absurd
.Void
→Bool
:absurd
.()
→()
:id
.()
→Bool
:yes
.()
→Bool
:no
.Bool
→()
:unit
.Bool
→Bool
:yes
.Bool
→Bool
:no
.Bool
→Bool
:id
.Bool
→Bool
:not
.
Note: yes
is a function that returns True
for all inputs, no
is a function that returns False
for all inputs,
and not
is a function that negates a boolean value.
3 Categories Great and Small
3.6 Challenges
3.6  1
Generate a free category from:
 A graph with one node and no edges
 A graph with one node and one (directed) edge (hint: this edge can be composed with itself)
 A graph with two nodes and a single arrow between them
 A graph with a single node and 26 arrows marked with the letters of the alphabet: a, b, c … z.
 Add the identity edge.
 Do nothing.
 For each node, add one identity edge.
 For each string that only consists of the alphabet with length that is not 1, add one edge.
3.6  2
What kind of order is this?
 A set of sets with the inclusion relation: A is included in B if every element of A is also an element of B.
 C++ types with the following subtyping relation:
T1
is a subtype ofT2
if a pointer toT1
can be passed to a function that expects a pointer toT2
without triggering a compilation error.
 Partial order.
 Partial order.
3.6  3
Considering that
Bool
is a set of two valuesTrue
andFalse
, show that it forms two (settheoretical) monoids with respect to, respectively, operator&&
(AND) and
(OR).
 For
&&
: Neutral value is
True
. a && True == True && a
.(a && b) && c == a && (b && c)
.
 Neutral value is
 For

: Neutral value is
False
. a  False == False  a
.(a  b)  c == a  (b  c)
.
 Neutral value is
3.6  4
Represent the
Bool
monoid with the AND operator as a category: List the morphisms and their rules of composition.
Morphisms:
id
:x && True
, The identity morphism.no
:x && False
, ReturnsFalse
for all inputs.
Rules of composition:
id
∘id
=id
.id
∘no
=no
.no
∘no
=no
.no
∘id
=no
.
3.6  5
Represent addition modulo 3 as a monoid category.
Morphisms:
plus_0
:(x + 0) % 3
, The identity morphism.plus_1
:(x + 1) % 3
.plus_2
:(x + 2) % 3
.
Rules of composition:
plus_0
∘plus_0
=plus_0
.plus_0
∘plus_1
=plus_1
.plus_0
∘plus_2
=plus_2
.plus_1
∘plus_0
=plus_1
.plus_1
∘plus_1
=plus_2
.plus_1
∘plus_2
=plus_0
.plus_2
∘plus_0
=plus_2
.plus_2
∘plus_1
=plus_0
.plus_2
∘plus_2
=plus_1
.
4 Kleisli Categories
4.4 Challenge
A function that is not defined for all possible values of its argument is called a partial function. It’s not really a function in the mathematical sense, so it doesn’t fit the standard categorical mold. It can, however, be represented by a function that returns an embellished type
optional
:;
For example, here’s the implementation of the embellished function
safe_root
:optional<double>
Here’s the challenge:
4.4  1
Construct the Kleisli category for partial functions (define composition and identity).
See here.
4.4  2
Implement the embellished function
safe_reciprocal
that returns a valid reciprocal of its argument, if it’s different from zero.
See here.
4.4  3
Compose the functions
safe_root
andsafe_reciprocal
to implementsafe_root_reciprocal
that calculatessqrt(1/x)
whenever possible.
See here.
5 Products and Coproducts
5.8 Challenges
5.8  1
Show that the terminal object is unique up to unique isomorphism.
Suppose we have two terminal objects t1 and t2. Since t1 is terminal, there must exists an unique morphism f from t1 to t2. Similarly, there must exists an unique morphism g from t2 to t1.
Now we show that f ∘ g is the identity morphism. First, since f is a morphism from t1 to t2, and g is a morphism from t2 to t1, f ∘ g must be a morphism from t1 to t1. Since t1 is a terminal object, there must be an unique morphism from t1 to t1, and since we are in a category, there must be an identity morphism form t1 to t1. So we must have f ∘ g being the identity morphism.
Similarly, g ∘ f must also be the identity morphism from t2 to t2. Now we have t1 and t2 are unique up to isomorphism. Since f and g are unique, we further have t1 and t2 are unique up to unique isomorphism.
5.8  2
What is a product of two objects in a poset? Hint: Use the universal construction.
A product of two objects a and b in a poset is the object c that c ≤ a and c ≤ b such that for any other object c′ that c′ ≤ a and c′ ≤ b, c′ ≤ c. In other words, the product of two objects is the largest object that is smaller than both a and b.
5.8  3
What is a coproduct of two objects in a poset?
A coproduct of two objects a and b in a poset is the object c that a ≤ c and b ≤ c such that for any other object c′ that a ≤ c′ and b ≤ c′, c ≤ c′. In other words, the coproduct of two objects is the smallest object that is greater than both a and b.
5.8  4
Implement the equivalent of Haskell
Either
as a generic type in your favorite language (other than Haskell).
See here.
5.8  5
Show that
Either
is a “better” coproduct thanint
equipped with two injections:int int
Hint: Define a function
int ;
that factorizes
i
andj
.
See here.
5.8  6
Continuing the previous problem: How would you argue that
int
with the two injectionsi
andj
cannot be “better” thanEither
?
If int
were better than Either
, there should exist a function m
from int
to Either
that factorizes the Left
and Right
function. Consider that the Left
function maps 0
to Left(0)
and the Right
function maps true
to
Right(0)
, m
∘ i
should behave like Left
and m
∘ j
should behave like Right
. But that is not possible,
because i
maps 0
to 0
, and j
maps true
to 0
, there is no way for m
to map 0
to both Left(0)
and
Right(true)
, so int
cannot be better than Either
.
5.8  7
Still continuing: What about these injections?
int int
Still not better than Either
. With Left
, I can map std::numeric_limits<int>::max()
to
Left(std::numeric_limits<int>::max())
(sorry for mixing Rust and C++ grammar, but you get the idea), but
i(std::numeric_limits<int>::max())
triggers signed integer overflow, which is undefined behavior. No m
function
can map undefined behavior to Left(std::numeric_limits<int>::max())
, so Either
is still better.
5.8  8
Come up with an inferior candidate for a coproduct of
int
andbool
that cannot be better thanEither
because it allows multiple acceptable morphisms from it toEither
.
Consider the (bool, i32)
tuple type with the following two injections:
I can have two functions from (bool, i32)
to Either
:
See here.
6 Simple Algebraic Data Types
6.5 Challenges
6.5  1
Show the isomorphism between
Maybe a
andEither () a
.
See here.
6.5  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 aShape
, we do it by pattern matching on the two constructors:area (Circle r) = pi * r * r area (Rect d h) = d * h
Implement
Shape
in C++ or Java as an interface and create two classes:Circle
andRect
. Implementarea
as a virtual function.
See here.
6.5  3
Continuing with the previous example: We can easily add a new function
circ
that calculates the circumference of aShape
. We can do it without touching the definition ofShape
:circ (Circle r) = 2.0 * pi * r circ (Rect d h) = 2.0 * (d + h)
Add
circ
to your C++ or Java implementation. What parts of the original code did you have to touch?
See here.
I have to update the definition of the Shape
interface and the implementation of Shape
for both Circle
and Rect
types.
6.5  4
Continuing further: Add a new shape,
Square
, toShape
and make all the necessary updates. What code did you have to touch in Haskell vs. C++ or Java? (Even if you’re not a Haskell programmer, the modifications should be pretty obvious.)
See here.
6.5  5
Show that a + a = 2 × a holds for types (up to isomorphism). Remember that 2 corresponds to
Bool
, according to our translation table.
See here.
7 Functors
7.4 Challenges
7.4  1
Can we turn the
Maybe
type constructor into a functor by defining:fmap _ _ = Nothing
which ignores both of its arguments? (Hint: Check the functor laws.)
No, because identity is not preserved. For example, fmap id (Just 4)
= Nothing
, while id (Just 4)
= Just 4
.
7.4  2
Prove functor laws for the reader functor. Hint: it’s really simple.

Preserve of identity:
fmap id x
=id . x
=x
. 
Composition:
We have:
fmap (f . g) x
=(f . g) . x
, and(fmap f . fmap g) x
=fmap f (fmap g x)
=fmap f (g . x)
=f . (g . x)
=(f . g) . x
.
So
fmap (f . g) x
=(fmap f . fmap g) x
.
7.4  3
Implement the reader functor in your second favorite language (the first being Haskell, of course).
See here.
7.4  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 (in other words, use induction).

Preservation of identity:

Nil
case:fmap id Nil
=Nil
. 
Cons x t
case:fmap id (Cons x t)
=Cons (id x) (fmap id t)
=Cons x (fmap id t)
=Cons x t
(by induction).So
fmap id (Cons x t)
=Cons x t
So
fmap id x
=x
. 

Preservation of composition:

Nil
case:We have
fmap (f . g) Nil
=Nil
, and(fmap f . fmap g) Nil
=fmap f (fmap g Nil)
=fmap f Nil
=Nil
.
So
fmap (f . g) Nil
=(fmap f . fmap g) Nil
. 
Cons x t
case:We have:
fmap (f . g) (Cons x t)
=Cons ((f . g) x) (fmap (f . g) t)
, and(fmap f . fmap g) (Cons x t)
=fmap f (fmap g (Cons x t))
=fmap f (Cons (g x) (fmap g t))
=Cons (f (g x)) (fmap f (fmap g t))
=Cons ((f . g) x) ((fmap f . fmap g) t)
=Cons ((f . g) x) (fmap (f . g) t)
(by induction).
So
fmap (f . g) (Cons x t)
=(fmap f . fmap g) (Cons x t)
.
So
fmap (f . g) x
=(fmap f . fmap g) x
. 
8 Functoriality
8.9 Challenges
8.9  1
Show that the data type:
data Pair a b = Pair a b
is a bifunctor. For additional credit implement all three methods of
Bifunctor
and use equational reasoning to show that these definitions are compatible with the default implementations whenever they can be applied.
See here.
bimap f g (a, b) = (f a, g b)
first f (a, b) = (f a, b)
second g (a, b) = (a, g b)

Proof of
bimap f g (a, b)
=(first f . second g) (a, b)
:bimap f g (a, b)
=(f a, g b)
(first f . second g) (a, b)
=first f (second g (a, b))
=first f (a, g b)
=(f a, g b)

Proof of
first f (a, b)
=bimap f id (a, b)
:first f (a, b)
=(f a, b)
bimap f id (a, b)
=(f a, id b)
=(f a, b)

Proof of
second g (a, b)
=bimap id g (a, b)
:second g (a, b)
=(a, g b)
bimap id g (a, b)
=(id a, g b)
=(a, g b)
8.9  2
Show the isomorphism between the standard definition of
Maybe
and this desugaring:type Maybe' a = Either (Const () a) (Identity a)
Hint: Define two mappings between the two implementations. For additional credit, show that they are the inverse of each other using equational reasoning.
See here.
maybeToEither Nothing = Left (Const ())
maybeToEither (Just a) = Right a
eitherToMaybe Left (Const ()) = Nothing
eitherToMaybe Right a = Just a
Proofs of maybeToEither
and eitherToMaybe
are the inverse of each other.

Proof of
maybeToEither (eitherToMaybe a)
=a
:maybeToEither (eitherToMaybe (Left (Const ())))
=maybeToEither Nothing
=Left (Const ())
maybeToEither (eitherToMaybe (Right a))
=maybeToEither (Just a))
=Right a

Proof of
eitherToMaybe (maybeToEither a)
=a
:eitherToMaybe (maybeToEither Nothing)
=eitherToMaybe (Left (Const ()))
=Nothing
eitherToMaybe (maybeToEither (Just a))
=eitherToMaybe (Right a))
=Just a
8.9  3
Let’s try another data structure. I call it a
PreList
because it’s a precursor to aList
. It replaces recursion with a type parameterb
.data PreList a b = Nil  Cons a b
You could recover our earlier definition of a
List
by recursively applyingPreList
to itself (we’ll see how it’s done when we talk about fixed points).Show that
PreList
is an instance ofBifunctor
.
See here.
8.9  4
Show that the following data types define bifunctors in
a
andb
:data K2 c a b = K2 c data Fst a b = Fst a data Snd a b = Snd b
For additional credit, check your solutions against Conor McBride’s paper Clowns to the Left of me, Jokers to the Right.
See here.
8.9  5
Define a bifunctor in a language other than Haskell. Implement
bimap
for a generic pair in that language.
See here.
8.9  6
Should
std::map
be considered a bifunctor or a profunctor in the two template argumentsKey
andT
? How would you redesign this data type to make it so?
Personal opinion: intuitively, a map
is like a function that maps the key type to the value type, so like a function,
it would seem that map
should be considered a profunctor. The problem is that the map
type from the standard library
is a mutable data structure, and I am not sure what the semantic of mutating mapped value should be, such as insertion
and removing.
The best I can come up with is this, only a getter is implemented.
9 Function Types
10 Natural Transformations
10.6 Challenges
10.6  1
Define a natural transformation from the
Maybe
functor to the list functor. Prove the naturality condition for it.
See here.
10.6  2
Define at least two different natural transformations between
Reader ()
and the list functor. How many different lists of()
are there?
See here.
There are infinite countable number of lists of ()
.
10.6  3
Continue the previous exercise with
Reader Bool
andMaybe
.
See here.
10.6  4
Show that horizontal composition of natural transformation satisfies the naturality condition (hint: use components). It’s a good exercise in diagram chasing.
We need to prove that for any
 category C, D and E,
 functor F: C → D,
 functor F′: C → D,
 natural transformation α: F → F′,
 functor G: D → E,
 functor G′: D → E,
 natural transformation β: G → G′,
 objects a and b in C,
 morphism f: a → b in C,
(β ∘ α) is a natural transformation from (G ∘ F) to (G′ ∘ F′), that is:
\[((G' ∘ F') f) ∘ (β ∘ α)_a = (β ∘ α)_b ∘ ((G ∘ F) f).\]
Let X = G ∘ F, Y = G′ ∘ F′, and γ = β ∘ α, we need to prove that:
\[(Y f) ∘ γ_a = γ_b ∘ X f\text{.}\]
Proof:
First, We apply \((Y f) ∘ γ_a\) to X a:
\(((Y f) ∘ γ_a) (X a)\)
= \((Y f) (γ_a (X a))\)
= \((Y f) (Y a)\)
= \(Y b\).
Then, we also apply \(γ_b ∘ (X f)\) to X a:
\((γ_b ∘ (X f)) (X a)\)
= \(γ_b ((X f) (X a))\)
= \(γ_b (X b)\)
= \(Y b\).
So indeed \((Y f) ∘ γ_a = γ_b ∘ X f\), we have proved that composition of natural transformations satisfies the naturality condition.
10.6  5
Write a short essay about how you may enjoy writing down the evident diagrams needed to prove the interchange law.
What?
10.6  6
Create a few test cases for the opposite naturality condition of transformations between different
Op
functors. Here’s one choice:op = Op (\x > x > 0)
and
f x = read x
See here.
Part Two
11 Declarative Programming
12 Limits and Colimits
12.5 Challenges
12.5  1
How would you describe a pushout in the category of C++ classes?
Assume morphisms are inheritance relation from subclasses to superclasses, if we have a diagram of class A
inheriting
from both B
and C
, then the pushout is a class D
that for any class E
that is the superclass of both B
and
C
, it is the super class of D
, that is, D
is the maximally common superclass of B
and C
.
12.5  2
Show that the limit of the identity functor Id :: C → C is the initial object.
The image of Id is C itself, which contains all objects in C, so the limit is a natural transformation, there exist a morphism from the limit to each object in C, since the natural transformation is universal, the morphisms from the limit to each object is unique, which satisfied the condition of the initial object.
12.5  3
Subsets of a given set form a category. A morphism in that category is defined to be an arrow connecting two sets if the first is the subset of the second. What is a pullback of two sets in such a category? What’s a pushout? What are the initial and terminal objects?
The pullback of two sets is their intersection set.
The pushout of two sets is their union set.
The initial object is the empty set.
The terminal object is the union set of all sets.
12.5  4
Can you guess what a coequalizer is?
The coequalizer is a colimit of a twoelement category with two parallel morphisms going between them.
12.5  5
Show that, in a category with a terminal object, a pullback towards the terminal object is a product.
The pullback of objects a and c with two morphisms:
 f: a → b
 g: c → b
is the object d with two morphisms:
 p: d → a
 q: d → c,
that for any object object d′ with two morphisms:
 p′: d′ → a
 q′: d′ → c
where f ∘ p′ = g ∘ q′, there is a unique morphism h: d′ → d, so that:
 p′: p ∘ h
 q′: q ∘ h
The trick is that b is a terminal object, both f ∘ p′ and g ∘ q′ must be the unique morphism from d′ → b, so the f ∘ p′ = g ∘ q′ condition is always satisfied. Without the constraint, d′ can be any object with any two morphisms:
 p′: d′ → a
 q′: d′ → c
Using the unique h morphism as the factoring morphism, we can satisfy the product condition, with d as the product of a and c.
12.5  6
Similarly, show that a pushout from an initial object (if one exists) is the coproduct.
The pushout of objects a and c with two morphisms:
 f: b → a
 g: b → c
is the object d with two morphisms:
 p: a → d
 q: c → d,
that for any object object d′ with two morphisms:
 p′: a → d′
 q′: c → d′
where p′ ∘ f = q′ ∘ g, there is a unique morphism h: d → d′, so that:
 p′: h ∘ p
 q′: h ∘ q
The trick is that b is an initial object, both p′ ∘ f and q′ ∘ g must be the unique morphism from b → d′, so the p′ ∘ f = q′ ∘ g condition is always satisfied. Without the constraint, d′ can be any object with any two morphisms:
 p′: a → d′
 q′: c → d′
Using the unique h morphism as the factoring morphism, we can satisfy the coproduct condition, with d as the coproduct of a and c.
13 Free Monoids
13.3 Challenges
13.3  1
You might think (as I did, originally) that the requirement that a homomorphism of monoids preserve the unit is redundant. After all, we know that for all a
h a * h e = h (a * e) = h a
So h e acts like a right unit (and, by analogy, as a left unit). The problem is that h a, for all a might only cover a submonoid of the target monoid. There may be a “true” unit outside of the image of h. Show that an isomorphism between monoids that preserves multiplication must automatically preserve unit.
An isomorphism between monoids A and B is a pair of morphisms
 f: A → B
 g: B → A
so that:
 g ∘ f is the identity morphism on A
 f ∘ g is the identity morphism on B
If f and g preserve multiplication, we have: for all a, b in A, f a × f b = f (a × b).
Assume e is the unit element in A, we need to prove that f e is the unit element in B, which means for all c in B, we need to have:
 f e × c = c
 c × f e = c
f e × c
= f e × (f ∘ g) c (Since f ∘ g is the identity morphism on B.)
= f e × f (g c)
= f (e × g c) (Since multiplication is preserved.)
= f (g c)
= (f ∘ g) c
= c (Since f ∘ g is the identity morphism on B.)
Similarly, we can prove that c × f e = c, so we provide that f e is the unit element in B, so unit is preserved.
13.3  2
Consider a monoid homomorphism from lists of integers with concatenation to integers with multiplication. What is the image of the empty list
[]
? Assume that all singleton lists are mapped to the integers they contain, that is[3]
is mapped to 3, etc. What’s the image of[1, 2, 3, 4]
? How many different lists map to the integer 12? Is there any other homomorphism between the two monoids?
 The image of the empty list
[]
is 1 since homomorphism preserves unit.  The image of
[1, 2, 3, 4]
is 24 since homomorphism preserves multiplication.  There lists map to integer 12 are lists that have total product of 12. There are infinite countable number of lists that have product of 12, since you can add 1 to the list any times you want without changing the product.
 We can also map lists of integers concatenation to integers with addition.
13.3  3
What is the free monoid generated by a oneelement set? Can you see what it’s isomorphic to?
It is lists that only contain that oneelement zero or more times. It’s isomorphic to natural numbers with addition where we map list to the length of the list.
14 Representable Functors
14.3 Challenges
14.3  1
Show that the homfunctors map identity morphisms in C to corresponding identity functions in Set.
For functor C(a, ), it maps a morphism f to a function that precomposes f on its argument:
(C(a, ) f) g = f ∘ g
So when applied to the identity morphism:
(C(a, ) id) g = id ∘ g = g
So the identity morphism is mapped to a function that just returns the argument, which is the identity function.
For contravariant functor C(, a), it maps a morphism f to a function that composes f to its argument:
(C(, a) f) g = g ∘ f
So when applied to the identity morphism:
(C(, a) id) g = g ∘ id = g
So the identity morphism is mapped to a function that just returns the argument, which is the identity function.
14.3  2
Show that
Maybe
is not representable.
For Maybe
to be representable, we need for create a function a → x
from a Maybe x
value for some representing
type a. The problem is that a Maybe x
value could be Nothing
, from which we are not able to create a function that
returns an x
value, so Maybe
is not representable.
14.3  3
Is the
Reader
functor representable?
Yes, trivially.
14.4  4
Using
Stream
representation, memoize a function that squares its argument.
Not sure if I understand the challenge correctly, but here is my attempt:
See here.
14.4  5
Show that
tabulate
andindex
forStream
are indeed the inverse of each other. (Hint: use induction.)
Wwe prove that both tabulate
∘ index
and index
∘ tabulate
are the identity function.
Let f = tabulate . index
, we have:
f (Cons x y)
= (tabulate . index) (Cons x y)
= tabulate (index (Cons x y))
= Cons (index (Cons x y) 0) (tabulate ((index (Cons x y)) . (+1)))
= Cons x (tabulate ((index (Cons x y)) . (+1)))
= Cons x (tabulate ((index (Cons x y)) . (+1)))
= Cons x (tabulate ((\n > if n == 0 then x else index y (n  1)) . (+1)))
= Cons x (tabulate (\n > if n + 1 == 0 then x else index y (n + 1  1)))
= Cons x (tabulate (\n > index y n))
= Cons x (tabulate (index y))
= Cons x (f y)
we know f
will preserve the first value, thus by induction on f y
, we know that it will also preserve the second
value, and also the third value, etc. So f
will preserve all values in a Stream
object, which means it is the
identity function.
Let g = index . tabulate
, we need to prove for any h
, g h = h
, which means for any x, g h x = h x
. We use proof
by induction on x
:
Base case, if x = 0
:
g h 0
= ((index . tabulate) h) 0
= index (tabulate h) 0
= index (Cons (h 0) (tabulate (h . (+1)))) 0
= (h 0)
Inductive cases, if x > 0
:
g h x
= (index . tabulate) h x
= index (tabulate h) x
= index (Cons (h 0) (tabulate (h . (+1)))) x
= index (tabulate (h . (+1))) (x  1)
(since x > 0)
= (index . tabulate) (h . (+1)) (x  1)
= g (h . (+1)) (x  1)
= (h . (+1)) (x  1)
(by induction)
= h ((+1) (x  1))
= h x
So for any x
, g h x = h x
, thus for any h
, g h = h
, which means g
is the identity function.
14.4  6
The functor:
Pair a = Pair a a
is representable. Can you guess the type that represents it? Implement
tabulate
andindex
.
The bool
type represents the Pair
functor.
See here.