#### Howdy, Stranger!

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

Options

# Question 3.2 - Catamorphisms

Consider the functor F:

data F a = Nil | Cons Int a deriving Functor

We define the recursive type:

type ListInt = Fix F

(a) Let isEven :: Int -> Bool take an integer to True if it is even, and False otherwise. Here is an F-algebra.

hello :: F Bool -> Bool

hello Nil = False

hello Cons n a = isEven n || a

What is the induced catamorphism cata hello :: List Int -> Bool?

(b) Implement the function product :: ListInt -> Int that takes a list of integers and returns their product.

• Options
1.

First, don't forget to include {-# language DeriveFunctor #-} at the beginning of your source code so you can derive Functor.

(a) cata hello takes a list of ints and returns true if there is at least one even number in the list. The first definition pattern matches with the empty list, returning False as a base case, the second definition checks if the current element is even. If n is even then it returns True, else it evaluates the next element. The recursive definition of this function would be:

or :: [Int] -> Bool

or [] = False

or (x:xs) = isEven x || or xs

(b)

product :: ListInt -> Int

product = cata prod

prod :: F Int -> Int

prod Nil = 1

prod (Cons n a) = n * a

Comment Source:First, don't forget to include {-# language DeriveFunctor #-} at the beginning of your source code so you can derive Functor. (a) cata hello takes a list of ints and returns true if there is at least one even number in the list. The first definition pattern matches with the empty list, returning False as a base case, the second definition checks if the current element is even. If n is even then it returns True, else it evaluates the next element. The recursive definition of this function would be: > or :: [Int] -> Bool > or [] = False > or (x:xs) = isEven x || or xs (b) > product :: ListInt -> Int > product = cata prod ------------------------------ > prod :: F Int -> Int > prod Nil = 1 > prod (Cons n a) = n * a
• Options
2.

When I try to use the ListInt type (defined as type ListInt = Fix F), I get errors. The compiler doesn't seem to be able to tell that an F a is also a Fix F.

For example, at the command line, Nil::ListInt gives me:

:82:1: error: • Couldn't match type ‘F a0’ with ‘Fix F’ Expected type: ListInt Actual type: F a0 • In the expression: Nil :: ListInt In an equation for ‘it’: it = Nil :: ListInt

Is anyone else getting these errors? Is it obvious what I'm doing wrong?

Comment Source:When I try to use the ListInt type (defined as type ListInt = Fix F), I get errors. The compiler doesn't seem to be able to tell that an F a is also a Fix F. For example, at the command line, Nil::ListInt gives me: <interactive>:82:1: error: • Couldn't match type ‘F a0’ with ‘Fix F’ Expected type: ListInt Actual type: F a0 • In the expression: Nil :: ListInt In an equation for ‘it’: it = Nil :: ListInt Is anyone else getting these errors? Is it obvious what I'm doing wrong?
• Options
3.

Ah, I figured it out, you have to use Fix before each data constructor, so like product (Fix Nil), or product $Fix$ Cons 2 $Fix$ Cons 5 $Fix Nil Comment Source:Ah, I figured it out, you have to use Fix before each data constructor, so like product (Fix Nil), or product$ Fix $Cons 2$ Fix $Cons 5$ Fix Nil
• Options
4.

Curious whether there's some simpler syntax that I'm missing.

Comment Source:Curious whether there's some simpler syntax that I'm missing.
• Options
5.

you can create an auxiliary function to create a ListInt from a list just to test things out:

toListInt :: [Int] -> ListInt

toListInt [] = Fix Nil

toListInt (x:xs) = Fix (Cons x (toListInt xs))

But I think the main idea of using cata and anamorphisms is that you never actually build these structures. So you would first create an anamorphism that induced a list of ints and then applies the catamorphism to calculate their product.

Basically you have a sequence of unfolding and folding that are fused together so that the list is never created, it just calculates the final result.

Comment Source:@EricRogstad you can create an auxiliary function to create a ListInt from a list just to test things out: > toListInt :: [Int] -> ListInt > toListInt [] = Fix Nil > toListInt (x:xs) = Fix (Cons x (toListInt xs)) But I think the main idea of using cata and anamorphisms is that you never actually build these structures. So you would first create an anamorphism that induced a list of ints and then applies the catamorphism to calculate their product. Basically you have a sequence of unfolding and folding that are fused together so that the list is never created, it just calculates the final result.