It looks like you're new here. If you want to get involved, click one of these buttons!

- All Categories 2.3K
- Chat 499
- Study Groups 17
- Petri Nets 8
- Epidemiology 3
- Leaf Modeling 1
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 339
- MIT 2019: Lectures 79
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 67
- Azimuth Code Project 110
- Statistical methods 3
- Drafts 2
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 147
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 707

Options

Natural numbers can be represented in Haskell as a recursive data structure

data Nat = Zero | Succ Nat

(a) Implement a type `Nat2`

, isomorphic to `Nat`

, but this time defined as an initial
algebra of a functor.

(b) Using a catamorphism, define a function `Nat2 -> Int`

that maps n to the n-th
Fibonacci number.

(c) Define a coalgebra whose anamorphism is a (partial) function `Int -> Nat2`

that
sends a non-negative Int into its fixed-point representation (ie. its representation
as a value of Nat2).

## Comments

a)

(Nat(X) = 1 + X)

b) You need the last two values to calculate the next Fibonacci number. So we can use a

`NatF (Int, Int)`

to store those values (I recently read about histomorphism that solve this issue!)c) You just need to map 0 to ZeroF and any other number x to the SuccF of x-1

`a) > data NatF a = ZeroF | SuccF a (Nat(X) = 1 + X) b) You need the last two values to calculate the next Fibonacci number. So we can use a `NatF (Int, Int)` to store those values (I recently read about histomorphism that solve this issue!) > nat2fib :: Nat -> Int > nat2fib n = fst $ cata fib n > fib :: NatF (Int, Int) -> (Int, Int) > fib ZeroF = (0, 1) > fib (SuccF (x,y)) = (y, x+y) c) You just need to map 0 to ZeroF and any other number x to the SuccF of x-1 > int2nat :: Int -> Nat > int2nat = ana coalg > coalg :: Int -> NatF Int > coalg 0 = ZeroF >coalg x = SuccF (x-1)`