Machine Problem: Data Types and Functors

Overview

The goal for this assignment is to get more comfortable with using custom data types, functors, applicative functors, and monads.

Working on the assignment

All your code for this assignment should go into a file named "MP3.hs" within the "src/mps" subdirectory in your repository.

Exercises

1. Given the type declaration:

   data Expr = Val Int | Add Expr Expr
   

   define a higher-order function:

   folde :: (Int -> a) -> (a -> a -> a) -> Expr -> a
   

   such that folde f g replaces each Val constructor in an expression by the function f, and each Add constructor by the function g.

2. Using folde, define a function "eval :: Expr -> Int" that evaluates an expression to an integer value, and a function "size :: Expr -> Int" that calculates the number of values in an expression.

3. An alternative way to make a list into an applicative functor is to have pure create an infinite list of copies of its argument, and the <*> operator apply each argument function to the corresponding argument value at the same position.

   Because functor and applicative instances already exist for the list, a common strategy is to define a "wrapper" type for which we can then proceed to define instances. ZipList, below, is such a wrapper type. Complete the following declarations to implement the idea described above:

   data ZipList a = Z [a] deriving Show
   
   instance Functor ZipList where
       -- fmap :: (a -> b) -> ZipList a -> ZipList b
       fmap g (Z xs) = ...
   
   instance Applicative ZipList where
       -- pure :: a -> ZipList a
       pure x = ...
   
       -- <*> :: ZipList (a -> b) -> ZipList a -> ZipList b
       (Z gs) <*> (Z xs) = ...
   

4. Relying on the State monad defined in class, define the "enqueue :: a -> State [a] ()" and "dequeue :: State [a] a" functions that provide queue semantics (as we did with the pop and push functions in class). Provide an example in a do block that demonstrates how these functions could be used to manipulate and use values stored on a queue within the state monad.

5. Given the following type of expressions:

   data Expr a = Var a | Val Int | Add (Expr a) (Expr a) deriving Show
   

   that contain variables of some type a, show how to make this type into instances of the Functor, Applicative, and Monad classes. With the aid of an example, explain what the >>= operator for this type does.