Skip to content

ProblemSet2.md

Latest commit

 

History

History
173 lines (106 loc) · 14.3 KB

ProblemSet2.md

File metadata and controls

173 lines (106 loc) · 14.3 KB

Problem set 2

Questions are from:

http://brendanfong.com/programmingcats_files/ps2.pdf

Question 1: Functors out of Set

  1. All sets are mapped to '1' and all morphims are mapped to

Because:

  1. Similarly, all sets can be mapped to '2' and all morphims are mapped to

  2. Also, all sets can be mapped to '3' and all morphims are mapped to

  3. is mapped to '1' and all sets mapped to '2'

Because

  • and for all Sets 's' which are not the empty set
  • All morphisms from the empty set to the empty set are mapped to , all morphisms from the empty set to a non empty set are mapped to 'a' and all morphisms from non empty set to non empty sets are mapped to . There are no morphisms from non empty set to the empty set (because the empty set does not have any target object).

For f : X → Y and g : Y → Z {\displaystyle g\colon Y\to Z, the possible compositions are:

X Y Z Proof
non empty set non empty set non empty set
empty set non empty set non empty set
empty set empty set non empty set

  1. is mapped to '1' and all sets mapped to '3' with all morphisms from the empty set to a non empty set are mapped to 'b . a'

  2. is mapped to '2' and all sets mapped to '3' and all morphisms from the empty set to a non empty set are mapped to 'b

Question 2. Constant functors

a. With all elements are mapped to set and all morphisms are mapped to the identity function so it is obvious the preservation of identities and composition laws are true.

b.

data BooleanFunctor a = BooleanFunctor Bool

instance Functor BooleanFunctor where
  fmap f (BooleanFunctor a) = BooleanFunctor a

Question 3. The naturality of the diagonal

a. is a natural transformation for with because:

b.

$ ghci
GHCi, version 7.10.3: http://www.haskell.org/ghc/  :? for help
Prelude> let diag x = (x,x)
Prelude> :show bindings
diag :: t -> (t, t) = _

Question 4. Uniqueness of universal objects

a. if t and t' are terminal then it exists 2 morphisms such as:

*

We can also define the following 2 morphisms:

So we have:

So t and t' are isomorphic

b. Using fst and snd from lecture 6 I can define an identity function from p=(a,b) to p'=(a,b):

The function also works from p' to p so p and p' are isomorphic

c. Both demonstrations rely on function composition

Question 5: Products in preorders

a. As 42 = 314 and 27 = 3 9, their product in that category is 3149 = 378. The operation is the lowest common denominator.

b. The product of {a,b,c} and {b,d,c} is {a,b,c,d}. The operation is the union on sets.

c. The product of true and false is 'true' (as true implies true and false implies true) so the operation is 'or'.

Question 6: Products in Hask

a. swap

swap :: (a,b) -> (b,a)
swap (a,b) = (b,a)

swap is an isomorphism because

b. unit

unit :: a -> ((),a)
unit a = ((),a)

unit is an isomorphism because

c. assoc

assoc :: (a,(b,c)) -> ((a,b),c)
assoc (x,(y,z)) = ((x,y),z)

assoc' :: ((a,b),c)) -> (a,(b,c))
assoc' ((x,y),z) = (x,(y,z))

assoc is an isomorphism because we can define a morphism assoc' such as

Question 7: The Product of Categories

F and G being functors we can define:

because

Question 8: Bifunctors

Implementation of 'bimap' for Either:

  bimapEither :: (a -> b) -> (c -> d) -> (Either a c) -> (Either b d)
  bimapEither f g (Left a) = Left (f a)
  bimapEither f g (Right c) = Right (g c)

Question 9: It is quite fascinating (but still very abstract) how the definition of product can be generalized.