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.

Comments

  • 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
  • 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?
  • 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`
  • 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.
  • 5.

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

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