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

- All Categories 2.3K
- Chat 500
- Study Groups 19
- Petri Nets 9
- Epidemiology 4
- 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 68
- Azimuth Code Project 110
- Statistical methods 4
- 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 713

Options

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.

## Comments

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:(b)

`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`

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?

`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?`

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`

`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``

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

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

@EricRogstad

you can create an auxiliary function to create a

`ListInt`

from a list just to test things out: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.

`@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.`