It looks like you're new here. If you want to get involved, click one of these buttons!
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)