Assignment 3  Higher-Order Functions and Lazy Evaluation

CMPT 340
Assignment 3 
Higher-Order Functions and Lazy Evaluation
Total: 100 Points
[Note: For each of the following problems you must explicitly include the function type signature.]
Problem 1 [15 + 15 Points]. A higher-order function unfold can be defined as follows to encapsulate a pattern
of recursion for producing a list:
unfold p h t x | p x = [ ]
| otherwise = h x : unfold p h t (t x)
That is, the function unfold p h t produces the empty list if the predicate p is true of the argument, and
otherwise produces a non-empty list by applying the function h to give the head, and the function t to
generate another argument that is recursively processed in the same way to produce the tail of the list. For
example, a functionint2bin (to convert integers to binary numbers) can be written as follows:
int2bin = unfold (==0) (`mod`2) ('div`2)
[Note: putting function names mod and div inside back quotes allows them to be used infix]
Define the following functions using unfold:
a) map f
b) iterate f, where iterate f x produces a list by applying the function f to x an increasing number of times, as
follows:
iterate f x = [x, f x, f (f x), f (f (f x)), ... ]
Problem 2 [20 Points]. Define a function altMap, which takes two functions (instead of the one for map) to
apply to a list. altMap alternately applies its two argument functions to the successive elements of the list,
the first function to the first element, the second function to the second element, and so on. For
example, altMap (+10) (+100) [0, 1, 2, 3, 4] evaluates to [10, 101, 12, 103, 14]
Problem 3 [10 Points]. Using altMap, define the function luhn :: [Int] - Bool for the Luhn algorithm, which was
assigned for Assignment 1.
Problem 4 [20 Points]. Show how the single comprehension [(x, y) | x <- [1, 2, 3], y <- [4, 5, 6]] with two
generators can be alternatively expressed using two comprehensions with single generators. [Hint: make use
of the library function concat :: [[a]] - [a], and nest one comprehension within the other.]
Problem 5 [20 Points]. A positive integer is perfect if it equals the sum of all of its factors, excluding the
number itself. For example, 6, 28, 496, and so on. Define a list comprehension to generate an infinite list of
perfect numbers. Do not make external function calls. Try to be efficient in the search for factors. [Hint: One
way to do this is by (1) placing a comprehension for finding factors in a qualifier of the the top-level
comprehension, (2) adding the factors using an appropriate higher-order function, and (3) checking to see
whether the sum equals the number.]
Submission:
Create a directory with your nsid as its name. Inside this directory, create separate sub-directories with
names like problem2, problem3, etc. for each programming problem. Under each programming problem's
folder, include a file with your program, as well as a text file showing a transcript of your testing of the
program.
Once you have everything in your directory, create a zip file for the entire directory. If your nsid is <your_nsid
name the zip file <your_nsid.zip. When opened, it should create a directory called <your_nsid.
You may submit multiple times before the deadline, so you are advised not to wait till the last minute to submit
your assignment to avoid system slowdown. You are encouraged to submit completed parts of the
assignment early. Late submissions will not be accepted.