Description
Task 1: Polymorphic Types (Haskell Only) 30 pts
In this section, you will implement some polymorphic functions involving Maybe and
Either. The type signature can serve as a big hint for the implementations.
(a) catMaybes and mapMaybe 10 pts
Recall the type constructor Maybe from lecture.
Maybe a = Nothing | Just a
Maybe takes a type parameter to produce a type. A value of type Maybe a is either
Nothing, or of the form Just x where x is a value of type a. For example, Nothing and
Just 3 are some values of type Maybe Int.
You will implement two functions catMaybes and mapMaybe.
• catMaybes takes a list of type [Maybe a] and returns a list of type [a]. In
particular, the output lists consists of the values of the Just elements. Nothing
elements of the input list are ignored. For example,
catMaybes [Just 1, Nothing, Just 3, Just 2, Nothing] = [1, 3, 2]
• mapMaybe takes a function f of type a -> Maybe b and a list of type [a] as input,
and returns a list of type [b]. In particular, f is applied to each element of xs
and values of the Just outputs are returned. Nothing outputs are ignored. For
example,
mapMaybe inv [2, 4, 0, -1] = [0.5, 0.25, -1]
where inv is defined as follows:
inv :: Float -> Maybe Float
inv 0 = Nothing
inv x = Just (1 / x)
1
(b) partitionEithers and mapEither 10 pts
The type constructor Either is defined by:
Either a b = Left a | Right b
Either takes two type parameter to produce a type. A value of type Either a b
is in one of two forms: Left x where x is a value of type a, or Right y where y is a
value of type b. For example, Left 1 and Right ’x’ are some values of type Either
Int Char.
You will implement two functions partitionEithers and mapEither.
• partitionEithers takes a list of type [Either a b] and returns a pair of lists of
type ([a], [b]). In particular, elements of the input type are separated into two
lists based on whether they use the data constructor Left or Right. For example,
partitionEithers [Left 2, Right ’x’, Right ’!’, Left 5]
= ([2, 5], [’x’, ’!’])
• mapEither takes as input a function of type a -> c, a function of type b -> c,
and a list of type [Either a b], and returns a list of type [c]. In particular, one
of the two functions is applied to each element of the list depending on whether
they use the data constructor Left or Right. For example,
mapEither even isAlpha [Left 2, Right ’x’, Right ’!’, Left 5]
= [True, True, False, False]
In the example above, even :: Integral a => Int -> Bool is imported from
Prelude and isAlpha :: Char -> Bool is imported from Data.Char.
(c) maybeToEither and eitherToMaybePair 10 pts
You will implement two functions maybeToEither and eitherToMaybePair.
To implement maybeToEither, you will need to know the Unit type. In Haskell, the
type () (i.e. the Unit type) is a type which has only one value, also referred to as ().
Note that the type and its unique value share a name, i.e. () :: ().
• maybeToEither takes a value of type Maybe a as input and returns a value of type
Either () a. If the input is a Just, the output will be a Left. If the input is
Nothing, the output will be a Right.
• eitherToMaybePair takes a value of type Either a b and returns a pair of type
(Maybe a, Maybe b), where exactly one of the elements is Nothing and the other
is a Just, depending on the input.
Task 2: Infinite Lists (Haskell Only) 20 pts
Suppose we want to create an infinite list consisting of a given element x. In your
experience with eagerly evaluated languages such as Racket and Python, you have likely
discovered that the following solution will not work.
2
(define (repeat x)
(cons x (repeat x)))
For example, if we try to evaluate car (repeat 0), Racket will try to evaluate
repeat 0 before passing it to car as an input. However, a call to repeat will never
terminate, so the program will hang (or throw a “RecursionError” in the case of Python).
By the magic of lazy evaluation, such a solution will actually work in Haskell.
repeat :: a -> [a]
repeat x = x : repeat x
Now, if we try to evaluate head (repeat 0), Haskell will not bother evaluating
repeat 0 right away. Rather, it will pass it to head, which will try to access its first
element. At this point, repeat 0 is called, which returns (0 : repeat 0). This makes
it clear that 0 is the first element, so head will return 0. There’s no need to access the
rest of the list, so it will not be evaluated.
In this task, you will get some practice with infinite lists as described here.
(a) infPower 10 pts
infPower takes an integer n as input and returns an infinite list containing all powers
of n, starting from 1. For example, infPower 2 == [1, 2, 4, 8, 16, …]. Assume
that n
0 = 1 for all n (in particular, 0
0 = 1).
(b) infFibonacci 10 pts
Define infFibonacci to be an infinite list containing the elements of the Fibonacci
sequence, i.e. infFibonacci == [1, 1, 2, 3, 5, 8, 13, …].
Hint: You may want to use zipWith in your implementation.
Task 3: Implement Functor Tree (Haskell Only) 20 pts
In this task, we will consider a Tree data structure.
data Tree a = Node a [Tree a]
Recall the type class Functor from lecture. Functor provides mapping with a function fmap. The function fmap also has the infix alias (<$>), i.e. fmap f x and f <$> x
are equivalent. See below for part of the definition of Functor in Prelude.
class Functor f where
fmap :: (a -> b) -> f a -> f b
To implement a type as an instance of Functor, we need to define the function fmap
for this type. For example, [] (i.e. the polymorphic list type) is declared as an instance
of Functor as follows:
instance Functor [] where
fmap :: (a -> b) -> [a] -> [b]
fmap _ [] = []
fmap f (x:xs) = f x : fmap f xs
Your task is to implement Tree as an instance of Functor.
3
By convention, the implementation of fmap should satisfy the Functor Laws. You are
given Property Tests in A3_Student_Tests.hs in order to verify that your implementation satisifes these properties. You are encouraged to read these tests and understand
why they are satisfied by your implementation.
Task 4: Macros (Racket Only) 30 pts
(a) my-first-macro 15 pts
You will implement a macro my-first-macro which produces lists of symbols and
strings. See the tests provided in the starter code for details.
Your solution will get full marks if it passes the three given tests and satisfies the
following properties:
• Your solution must not literally contain the symbols ’A, ’X, ’Y, or ’Z.
• Your solution must not use a new define (except for the the given defines).
Hint: It might help to look up functions symbol->string and string->symbol.
(b) def-func 15 pts
The macro def-func will provide a new syntax for defining simple tail recursive
functions. Consider the following function factorial-tail from Assignment 1 with a
small modification to the base cases.
(define (factorial-tail n acc)
(cond [(<= n 0) 0]
[(= n 1) acc]
[(factorial-tail (- n 1) (* acc n))]))
We want to define a macro that allows us to use the following python-like definition
to define this function.
(def-func factorial-tail (n acc) :
base ([(<= n 0) -> 0]
[(= n 1) -> acc])
rec (- n 1) (* acc n))
The words and symbols indicated by red are reserved keywords by the macro. They
are declared as such in the starter code. The base keyword is followed by the base case
conditions and outputs. The rec keyword is followed by the inputs to the recursive call
(to the same function being defined).
Hint: In Racket, you can use … to bind multiple values to the same identifier. You
should look up more information on this!
Submission and Instructions
Submit the files a3.rkt and A3.hs to Markus. Make sure to complete all sections
labeled “Complete me” in a3.rkt and “undefined” in A3.hs.
4
For all assignments:
• You are responsible for making sure that your code has no syntax errors or compile
errors. If your file cannot be imported in another file, you may receive a grade of
zero.
• If you’re not intending to complete one of the functions, do not remove the function
signature. If you are including a partial solution, make sure it doesn’t cause a
compile error. If your partial solution causes compiles errors, it’s better to comment
out your solution (but not the signature).
• In Racket, you may not use any iterative or mutating functionality unless explicitly
allowed. Iterative functions in Racket are functions like loop and for. Mutating
functions in racket have a ! in their names, for example set!. If you use the
materials discussed in class and do not go out of your way to find these functions,
your code should be okay.
• Do not modify the (provide …) (in Racket) and module (…) where (in
Haskell) lines of your code. These lines are crucial for your code to pass the tests.
