Skip to content

Latest commit

 

History

History
170 lines (131 loc) · 11.7 KB

ProblemSet1.md

File metadata and controls

170 lines (131 loc) · 11.7 KB
Raw

Problem set 1

Questions are from:

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

Question 1: Functions in Haskell

$ ghci
GHCi, version 7.10.3: http://www.haskell.org/ghc/  :? for help
Prelude> let f x = x ^ 2
Prelude> f 6
36
Prelude> let g x = x + 1
Prelude> let h = f . g
Prelude> h 2
Prelude> let i = g . f
Prelude> i 2
5

Question 2: Tiny Category

Ob(c) = { 1,2 }

4 morphisms

  4. {

There are only 4 possible compositions:

  1. f . id1
  2. id2 . f
  3. id1 . id1 1 id2 . id2

And because of the definition of f, id1 and id2 we have:

  1. f . id1 (1) = f(1) so as 1 is the only possible value for f, f . id1 = f
  2. id2 . f (1) = id2(2) = 2 = f(1) so as 1 is the only possible value for f, id2 . f = f

Associativity is also trivial:

  1. (f . id1) . id1 = f . id1 = f . (id1 . id1)

Question 3 : Isomorphism ?

Yes

  • f . g (d) = f(c) = d so f . g = id for d
  • g . f (c) = g(d) = c so g . f = id for c

Question 4: Almost categories

data with associative law but no unit law

  • all morphisms are identity but as does not exist, the unit law does not hold

data with no associative law but with unit law

  • Unit law is verified by
  • Associative law does not work for the following example:

Question 5: Monoids

(a)

is a monoid because 0 is the unit for the addition and the addition is associative

(b)

is a monoid because

  • adding an empty string to a string doesn't change the initial string (Unit law)
  • concatenation is associative

(c)

For every monoid we can create a category such as:

Unit: We have (demonstrating the other rule is exactly the same)

Associative:

Question 6: Preorders

a)

1 is the identify

b)

If is a morphism then it exists such as

Similarly it exists such as

So we have which means is a morphism

c)

There is an issue with 0 because () so there is more than one morphism so it cannot be a pre order.

Question 7: Church Booleans

I tried 2 different ways to evaluate the expressions:

  • (AND True) False = ((\p (\q (pq) p) True) False = ((\q (False q) False) True) = (False True) False = ((\x (\y x)) True) False = (\y False) True = False

  • (OR False) =(\p (\q (pp)q)) \x (\y y) =(\q ((\x (\y y)) \x2 (\y2 y2)) q) =(\q (\y y) q)

(OR False) True =(\q (\y y) q) =(\y y) \x (\y2 x) = \x (\y x) = True

Question 8: Y Combinator

Y g = \f ((\x f(x x))(\x f(x x))) g

Y g = ((\x g(x x))(\x g(x x)))

Y g = g(\x g(x x) \x g(x x))

Y g = g(Y g)

so if replace again Y g on the right by its value:

Y g = g(g(Y g))

and so on: Y g = g(g(g ....g(g(Y g)))))...

Y g computes the fixed point of g

Question 9: Toy Category

data Objects = One | Two
data Functions = Id1 | Id2 | F

instance Category Objects Functions where
  dom mor = case mor of
    Id1 -> One
    Id2 -> Two
    F -> One
  cod mor = case mor of
    Id1 -> One
    Id2 -> Two
    F -> Two
  idy obj = case obj of
    One -> Id1
    Two -> Id2
  cmp m1 m2 = case (m1,m2) of
    (Id1,Id1) -> Just Id1
    (Id1,Id2) -> Nothing
    (Id2,Id1) -> Nothing
    (Id2,Id2) -> Just Id2
    (Id1,F) -> Nothing
    (Id2,F) -> Just F
    (F,Id1) -> Just F
    (F,Id2) -> Nothing
    (F,F) -> Nothing