Howdy, Stranger!

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

Options

Question 3.3 - Naturals

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).

• Options
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) Comment Source: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)