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

Comments

  • 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)
Sign In or Register to comment.