Skip to content

Latest commit

 

History

History
176 lines (112 loc) · 10.7 KB

ProblemSet3.md

File metadata and controls

176 lines (112 loc) · 10.7 KB
Raw

Problem set 3

Questions are from:

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

Question 1: Pullbacks and limits

As A is the constant category the definition of and is quite straightforward:

a. The object is and

b. The object is and

c. The object is and

Question 2. Catamorphisms

a. 'hello' returns 'True' if the list contains at least one even number and false is all the numbers it contains are odd.

b. implementation of 'product':

product :: F Int -> Int
product :: Nil = 1
product :: Cons n a = n * a

Question 3. Naturals

a. type Nat2

data Nat2 a = Zero | Succ a
  deriving Functor

b. Fibonnacci

fiboF :: (Nat2 (Int,Int)) -> (Int,Int)
fiboF ZeroF = (1,0)
fiboF (SuccF (n,m)) = (n+m,n)

fibo :: Fix Nat2 -> Int
fibo = fst . (cata $ fiboF)

c. coalgebra

coalg :: Int -> Nat2 Int
coalg 0 = ZeroF
coalg n = SuccF (pred n)

Question 4. Sort

-- https://hackage.haskell.org/package/data-fix-0.2.0/docs/Data-Fix.html
import Data.Fix

type Tree a = Fix (T a)

data T a b = Leaf | Node a b
  deriving Functor

splitCoAlgrebra :: [a] -> T [a] [a]
splitCoAlgrebra [] = Leaf
splitCoAlgrebra s = Node s1 s2 where (s1,s2) = split(s)

mergeAlgebra :: Ord a => T [a] [a] -> [a]
mergeAlgebra Leaf = []
mergeAlgebra (Node s1 s2) = merge s1 s2

main = print (hylo mergeAlgebra splitCoAlgrebra [3,1,4,1,5,9])

Question 5. Monoids as List algebras

a. Given a list algebra , we can define a monoid on the set X with:

  • e is such that and Associativity:

Identity

b. Given a monoid we can construct a list algrebra which uses the monoid to 'accumulate' all the x in the list in a final item x:

Where head is the first element of the list and tail the rest of the list. If the list only has one element then:

c. The monoid can be used to build lists of elements while the algebra reduces the list to an element.

Question 6 Hello World

main :: IO ()
main = print "hello"

Question 7 The tree monad

As Applicative is a superclass of Monad and Functor a superclass of Applicative, all 3 are implemented.

  data Tree a = Leaf a | Node (Tree a) (Tree a) 
    deriving Show

instance Functor Tree where
    fmap f (Leaf v) = Leaf (f v)
    fmap f (Node t1 t2) = Node (fmap f t1) (fmap f t2)

instance Applicative Tree where
   pure v = Leaf v
   (<*>) (Leaf f) (Leaf v) = Leaf (f v)
   (<*>) (Leaf f) (Node t1 t2) = Node (fmap f t1) (fmap f t2)
   (<*>) (Node t1 t2) t3 = Node (t1 <*> t3) (t2 <*> t3)


instance Monad Tree where
    return v = Leaf v
    (Leaf v) >>= f = (f v)
    (Node t1 t2) >>= f = Node (t1 >>= f) (t2 >>= f)

Question 9 Continuation monad

a. Continuation Functor

instance Functor (Cont s) where
  fmap f (Cont f2) = Cont (f2 . (\f3 -> f3 . f ))

instance Applicative (Cont s) where
  pure v = Cont (\f -> f v)
  (Cont fab) <*> (Cont f2) = Cont (\f -> (f2  (\a -> fab (\f3 -> f(f3(a))))))

instance Monad (Cont s) where
  return v = Cont (\f -> f  v)
  (Cont f1) >>= c2 = Cont (\f -> f1 (\a -> applyCont (c2 a) f))