Lab 4: Generating Lists by Recursion CIS 252: Introduction to Computer Science
The purpose of this lab is to give you practice with writing recursive functions in Haskell.
You may work singly or in pairs on this lab: If you work with a partner, turn in a
single solution with both names on it.
1 Towards Recursion
Each of the following functions takes an Integer as input and returns a list of
Integers as a result (you do not need to type these, but you can if you want):
listOfZero :: Integer -> [Integer]
listOfZero item = []
listOfOne :: Integer -> [Integer]
listOfOne item = item : listOfZero item
listOfTwo :: Integer -> [Integer]
listOfTwo item = item : listOfOne item
listOfThree :: Integer -> [Integer]
listOfThree item = item : listOfTwo item
listOfFour :: Integer -> [Integer]
listOfFour item = item : listOfThree item
The function listOfZero creates a list with zero copies of item by simply return-
ing the empty list. The function listOfOne creates a list with one copy of item by
placing one copy of item on the front of a zero-item list. The function listOfTwo
creates a list of two items by placing a single item on the front of a one-item list,
and the function listOfThree creates a list of three items by placing a single item
on the front of a two-item list. The function listOfFour works similarly.
We can generalize this idea to handle any integer n > 0: to create a list of n items, we
place a single item on the front of a list of n−1 items. The following function implements
this idea, accepting an extra argument to indicate the desired length of the list:
listOf :: Int -> Integer -> [Integer]
listOf n item
| n == 0 = []
| n > 0 = item : listOf (n-1) item
| otherwise = error “listOf: requires nonnegative input”
2 Pieces of a Recursive Function
In general, recursive functions have at least two separate cases:
1. The base case(s), which are the “stopping” cases
The base cases are those cases where the function gives a value directly, without
making additional recursive calls (i.e., calls to itself). The base case of listOf
is the “n == 0” case: when n = 0, listOf simply returns the empty list [].
2. The recursive case(s)
In the recursive cases, the function combines a partial answer with the result of
a recursive call. The recursive cases of listOf are the n > 0 cases: for each
such n, listOf places a single copy of item at the front of the result of the
recursive call.
Sometimes, a function will also include code to handle “bad/nonsense input” cases. For
example, what would it mean to create a list of −5 items? Thus, our function listOf
includes a case (via the otherwise guard) to handle problematic input more grace-
fully. Generally speaking, it’s best to check for “bad” input cases first; I violated this
strategy in listOf so as to focus your attention on the recursive essentials.
Before continuing to the next section, try out the listOf function on a few cases, to
convince yourself that it works as advertised:
listOf 0 8
listOf 5 8
listOf (-3) 8
3 Identifying the Cases
A good strategy for writing recursive functions is to employ Polya’s strategy: work out
a few examples by hand, including very simple examples and more complicated ones.
• The very simple cases are apt to show up as base cases for the recursion (depend-
ing on the function, there may be more than one base case).
• The more complicated examples are apt to illustrate a pattern that points towards
how the problem can be solved in a recursive way.
Page 1 Spring 2017
Lab 4: Generating Lists by Recursion CIS 252: Introduction to Computer Science
For example, recall the series of functions in Section 1 to create lists of items. Creating
a list of zero items was extremely easy—the function just returned the empty list. This
simple case ended up as the base case in our recursive function listOf.
Creating longer lists took a little more work, but it was still a pretty easy process. We
could create a 1-item list by placing a single item on the front of a list of length zero;
likewise, we could create a 2-item list by placing a single item on the front of a list of
length one. By the time we got to the 3-item list, we had identified a consistent pattern
for building larger lists from smaller ones.
An example Now, suppose we want to write a function altListOf that is similar to
listOf, except that it takes two items and alternates them. For example, altListOf
5 111 222 should return a list of length five whose values alternate between 111 and
222 (i.e., [111,222,111,222,111]).
The first question we should ask ourselves is: How should this function behave on some
typical inputs? We can identify some specific examples, such as the following:
• In the case of altListOf 0 111 222, the desired result is [].
• In the case of altListOf 1 111 222, the desired result is [111], which is
equivalent to 111:[]. Thus, it can be obtained by placing a copy of the first item
at the front of a list of length 0. (Likewise, the desired result of altListOf
1 222 111 is [222], which is equivalent to 222:[].)
• In the case of altListOf 2 111 222, the desired result is [111,222],
which is equivalent to 111:[222]. Thus, it can be obtained by placing a copy
of the first item at the front of a 1-element list that starts with the second item.
(Likewise, the desired result of altListOf 2 222 111 is [222,111],
which is equivalent to 222:[111].)
• In the case of altListOf 3 111 222, the desired result is
[111,222,111], which is equivalent to 111:[222,111]. Thus, it can
be obtained by placing a copy of the first item at the front of a 2-element list that
starts with the second item. (Likewise, the desired result of altListOf 3
222 111 is [222,111,222], which is equivalent to 222:[111,222].)
At this point, you may recognize the pattern (sometimes you may need additional cases),
and we try the following code:
altListOf :: Int -> Integer -> Integer -> [Integer]
altListOf n item1 item2
| n == 0 = []
| n > 0 = item1 : altListOf (n-1) item2 item1
| otherwise = error “altListOf: requires nonnegative input”
The main difference between this code and listOf is the addition of a second item,
plus the order of parameters in the recursive call: each time we make a recursive call, we
flip the order of the two items, so that the embedded list starts with the opposite item.
4 Your Problems
1. Write a Haskell function
cycle3 :: Int -> Integer -> Integer -> Integer -> [Integer]
such that cycle3 n item1 item2 item3 creates a list of length n, repeat-
edly cycling among item1, item2 and item3; Your function should report an
error if n is less than 0. For example, cycle3 8 10 20 30 should return the
list [10,20,30,10,20,30,10,20].
2. Write a Haskell function
switchback :: Int -> Integer -> Integer -> [Integer]
such that switchback n item1 item2 returns a list of length n, with
the following pattern: there is one copy of item1, followed by two
copies of item2, followed by two copies of item1, followed by two
copies of item2, and so on. Your code should raise an error if n is
less than 0. For example, switchback 15 0 77 should return the list
[0,77,77,0,0,77,77,0,0,77,77,0,0,77,77].
Hint: For this problem, have two base cases (one for n = 0 and one for n = 1);
for n > 1, employ a strategy similar to that used in altListOf.
What to hand in: Hand in the source code for your two functions, along with a clean
transcript that demonstrates convincingly that the code works as required. (For the
transcript, it suffices to save the *haskell* buffer to a file and then print out that file.)
Include a disclosure cover sheet, and complete all items on it (or you may lose points).
How/when to hand it in: This lab is due by noon on Friday, February 10. You should
submit the code and transcript in lab, lecture, or to the labeled bin near CST 4-226.
Page 2 Spring 2017
Towards Recursion
Pieces of a Recursive Function
Identifying the Cases
Your Problems