PS3: Racket List Recursion
 Due: 11:59pm Wednesday 22 February
 Notes:
 This pset has lots Racket programming. Start soon.
 This pset contains two solo problems (Problems 1 and 2).
 You should be able to do all of the problems after the Wed. Feb 15 class.
 The problems needn’t be done in order. Feel free to jump around.
 Submission:
 In your yourFullName CS251 Spring 2017 Folder, create a Google Doc named yourFullName CS251 PS3.
 At the top of your yourFullName CS251 PS3 doc, include your name, problem set number, date of submission, and an approximation of how long each problem part took.
 For all parts of all problems, include all answers (derivations, code, etc.) in your PS3 google doc. Please format all code and all evaluation derivations so that they’re easy to read. Format smallstep derivations and Racket code using a fixedwidth font, like Courier New or Consolas. You can use a small font size if that helps.
 For Problem 1 (Solo Problem: Alternative If Semantics), include your explanation and your smallstep derivation in your PS3 doc.
 For Problem 2 (Solo Problem: Recursive Numeric Functions)
 Be sure that all function definitions in
yourAccountNameps3solofunctions.rkt
also appear in your PS3 Doc (so that I can comment on them)  Drop a copy of your
yourAccountNameps3solofunctions.rkt
in your~/cs251/drop/ps03
drop folder on cs.wellesley.edu.
 Be sure that all function definitions in
 For Problem 3 (Boxandpointer diagrams), include all expressions in your PS3 doc.
 For Problem 4 (Recursive Racket List Functions):
 Be sure that all function definitions in
yourAccountNameps3listfunctions.rkt
also appear in your PS3e Doc (so that I can comment on them)  Drop a copy of your
yourAccountNameps3listfunctions.rkt
in your~/cs251/drop/ps03
drop folder on cs.wellesley.edu.
 Be sure that all function definitions in
1. Solo Problem: Alternative If Semantics (5 points)
This is a solo problem. This means you must complete it entirely on your own without help from any other person and without consulting resources other than course materials or online documentation. You may ask Lyn for clarification, but not for help.
The smallstep reduction rules for if
expressions in Racket are
(if V_test E_then E_else) ⇒ E_then
, ifV_test
is a value that is not#f
[if nonfalse](if #f E_then E_else) ⇒ E_else
[if false]
Lois Reasoner thinks that the reduction of if
expressions should be changed to:
(if V_test V_then V_else) ⇒ V_then
, ifV_test
is a value that is not#f
[if nonfalse Lois](if #f V_then V_else) ⇒ V_else
[if false Lois]
These differ from the actual rules by requiring that all three subexpressions e_test
, e_then
, and e_false
of (if e_test e_then e_false)
are first evaluated to values before the if
expression can be simplified.
Explain that Lois’s alternative semantics for if
are a bad idea. In particular, consider the sumbetween
function from PS2:
(define sumbetween
(lambda (lo hi)
(if (> lo hi)
0
(+ lo (sumbetween (+ lo 1) hi)))))
Use Lois’s semantics for if
in a smallstep semantics derivation for the evaluation of (sumbetween 2 3)
to explain what happens. You needn’t show every step, but at the very least should show lines in which the redex is λ_sb
applied to two values.
2. Solo Problem: Recursive Numeric Functions (20 points)
This is a solo problem. This means you must complete it entirely on your own without help from any other person and without consulting resources other than course materials or online documentation. You may ask Lyn for clarification, but not for help.
This problem involves the following recursive Racket function g
:
(define g
(lambda (n)
(if (<= n 2)
n
(+ n
(g (thirdish n))
(g (half n))))))
where thirdish
and half
are defined as
(define thirdish
(λ (int) (* (remainder int 3) (quotient int 3))))
(define half
(λ (int) (quotient int 2)))
half
returns the integer quotient of a number by 2 (e.g. (half 10)
and (half 11)
are both 5) and thirdish
returns the product of the integer quotient of the number by 3 and its remainder by three. For example:
> (map (λ (n) (cons n (thirdish n))) (range 12))
'((0 . 0) (1 . 0) (2 . 0) (3 . 0) (4 . 1) (5 . 2) (6 . 0) (7 . 2) (8 . 4) (9 . 0) (10 . 3) (11 . 6))

(8 points) Use smallstep semantics to derive the evaluation of
(g 11)
. To keep the size of your derivation manageable, use the same conventions used in smallstep derivations in PS2 Problem 4 Sum Fun. In particular:
Use the notation λ_g as an abbreviation for the
lambda
expression(lambda (n) (if (<= n 2) n (+ n (g (thirdish n)) (g (half n)))))

Use ⇒* to show only the steps of the derivation in which the redex is a call to λ_g.

Treat
half
andthirdish
as black boxes: do not show any redexes involving calls to these functions, only the results of such calls.


(1 point) How many times is
g
called in the evaluation of(g 11)
? (Be sure to include all base case calls, such as(g 0)
,(g 1)
, and(g 2)
.) 
(1 point) What is the maximum stack depth (measured in terms of maximum number of nested
+
operations) in the evaluation of(g 11)
? 
(5 points) Define a recursive Racket function named
numgcalls
that takes a single integer argumentn
and returns the number of times that the functiong
is called in the evaluation of(g n)
. Notes:
Define the
numgcalls
function in a new file namedyourAccountNameps3solofunctions.rkt
that you create in Dr. Racket. This file should also include the definitions ofhalf
andthirdish
from above. 
(numgcalls 11)
should return your answer from part b. 
You should only use Racket language features you used in PS2 or learned in the lectures on Racket expressions and declarations and Racket functions

Do not attempt to modify the definition of
g
so that it counts the number of timesg
is called by changing the contents of a global variable. 
Instead, write a new recursive function
numgcalls
that is very much likeg
, but rather than returning the number calculated byg
instead returns the number of calls tog
made in that calculation. Your definition should use the helper functionshalf
andthirdish
. 
Test your function using this expression, and include its result in your writeup:
(map (λ (n) (cons n (numgcalls n))) (range 100))


(5 points) Define a recursive Racket function named
maxdepthg
that takes a single integer argumentn
and returns the maximum stack depth (measured in terms of maximum number of nested+
operations) in the evaluation of(g n)
. Notes:
Add the
maxdepthg
function to youryourAccountNameps3solofunctions.rkt
file. 
(maxdepthg 11)
should return your answer from part c. 
You should only use Racket language features you used in PS2 or learned in the lectures on Racket expressions and declarations and Racket functions

The
max
function is especially useful here. 
Do not attempt to modify the definition of
g
so that it determines the stack depth by changing the contents of a global variable. 
Instead, write a new recursive function
maxdepthg
that is very much likeg
, but rather than returning the number calculated byg
instead returns the maximum stack depth in that calculation. Your definition should use the helper functionshalf
andthirdish
. 
Test your function using this expression, and include its result in your writeup:
(map (λ (n) (cons n (maxdepthg n))) (range 100))

3. Boxandpointer diagrams (10 points)
Consider the following boxandpointer diagram for the list structure named a
:

For each of the numbers 1 through 6, write a Racket expression that uses
car
andcdr
to extract that number froma
. 
Write down the printed representation for a (i.e., what would be returned by the Racket interpreter for evaluating
a
?). 
Write a Racket definition of the form
(define a
expr)
, where expr is an expression usingcons
,list
,
and the numbers 1 through 6 (but noquote
or quotation) to create the structure depicted in the diagram. (Once you have defineda
in this way, you may test your expressions from part (a).)
4. Recursive Racket List Functions (65 points)
In PS2, you wrote some recursive Racket functions that manipulate numbers. Here, you will continue to practice defining recursive Racket functions, but now you focus on functions that manipulate Racket lists. Unlike list and array data structures in many other languages, which are most naturally processed with loops, the linkedlist recursivelydefined nature of Racket lists make them natural candidates for recursive processing.
For each of the following Racket function specifications, write and test a recursive function that satisfies that specification. In all of your definitions, you should use the following recursive problem solving strategy:

For which argument(s) is the function so simple that the answer can be returned immediately? This is the base case.

For the other case(s) (known as the general case(s) or recursive case(s)), use divide/conquer/glue:

divide: make one or more subproblems that are smaller instances of the given problem;

conquer: assume that the recursive function you’re defining simply works and returns the correct answer on all of the smaller problems.

glue: combine the result(s) of the recursive function call(s) with information in the original problem to create the correct result for the whole problem.

Notes:

For this problem, you should use Dr. Racket to create a single file named
yourAccountNameps3listfunctions.rkt
that contains all the functions (including helper functions) that you define for this problem. 
In your definitions, unless otherwise instructed, you should not introduce any recursive helper functions. (But you can define nonrecursive helper functions).

If the following error message pops up during the testing of one of your functions, it mostly likely means that you have an infinite recursion that doesn’t reach its base case and runs out of memory due to a stack depth that cannot fit into available memory.

(5 points) Define a function
mapremainder
that takes two arguments (an integerdivisor
and a listints
of integers) and returns an integer list the same length asints
in which every element is remainder of dividing the corresponding element ofints
bydivisor
.> (mapremainder 2 (list 16 23 42 57 64 100)) '(0 1 0 1 0 0) > (mapremainder 3 (list 16 23 42 57 64 100)) '(1 2 0 0 1 1) > (mapremainder 5 (list 16 23 42 57 64 100)) '(1 3 2 2 4 0) > (mapremainder 17 (list 16 23 42 57 64 100)) '(16 6 8 6 13 15)

(5 points) Define a function
filterdivisibleby
that takes two arguments (an integerdivisor
and a listints
of integers) and returns a new integer list containing all the elements ofints
that are divisible bydivisor
. Usedivisibleby?
from above to determine divisibility.> (filterdivisibleby 2 (list 16 23 42 57 64 100)) '(16 42 64 100) > (filterdivisibleby 3 (list 16 23 42 57 64 100)) '(42 57) > (filterdivisibleby 4 (list 16 23 42 57 64 100)) '(16 64 100) > (filterdivisibleby 5 (list 16 23 42 57 64 100)) '(100) > (filterdivisibleby 17 (list 16 23 42 57 64 100)) '()
Use the following helper function, which is helpful in this problem and some of the following ones.
(define divisibleby? (lambda (num divisor) (= (remainder num divisor) 0)))

(5 points) Define a function
containsmultiple?
that takes an integerm
and a list of integersns
that returns#t
ifm
evenly divides at least one element of the integer listns
; otherwise it returns#f
. Usedivisibleby?
from above to determine divisibility.> (containsmultiple? 5 (list 8 10 14)) #t > (containsmultiple? 3 (list 8 10 14)) #f > (containsmultiple? 5 null) #f

(5 points) Write a function
allcontainmultiple?
that takes an integern
and a list of lists of integersnss
(pronounced “enziz”) and returns#t
if each list of integers innss
contains at least one integer that is a multiple ofn
; otherwise it returns#f
. Usecontainsmultiple?
in your definition ofallcontainmultiple?
.> (allcontainmultiple? 5 (list (list 17 10 2) (list 25) (list 3 8 5))) #t > (allcontainmultiple? 2 (list (list 17 10 2) (list 25) (list 3 8 5))) #f > (allcontainmultiple? 3 null) #t ; said to be "vacuously true"; there is no counterexample!

(5 points) Define a function
mapcons
that takes any valuex
and an nelement listys
and returns an nelement list of all pairs'(x . y)
wherey
ranges over the elements ofys
. The pair'(x . y)
should have the same relative position in the resulting list asy
has inys
.> (mapcons 17 (list 8 5 42 23)) '((17 . 8) (17 . 5) (17 . 42) (17 . 23)) > (mapcons 3 (list (list 1 6 2) (list 4 5) (list) (list 9 6 8 7))) '((3 1 6 2) (3 4 5) (3) (3 9 6 8 7)) > (mapcons 42 null) '()

(8 points) Define a function
mycartesianproduct
that takes two listsxs
andys
and returns a list of all pairs'(x . y)
wherex
ranges over the elements ofxs
andy
ranges over the elements ofys
. The pairs should be sorted first by thex
entry (relative to the order inxs
) and then by they
entry (relative to the order inys
).> (mycartesianproduct (list 1 2) (list "a" "b" "c")) ; yes, Racket has string values '((1 . "a") (1 . "b") (1 . "c") (2 . "a") (2 . "b") (2 . "c")) > (mycartesianproduct (list 2 1) (list "a" "b" "c")) '((2 . "a") (2 . "b") (2 . "c") (1 . "a") (1 . "b") (1 . "c")) > (mycartesianproduct (list "c" "b" "a") (list 2 1)) '(("c" . 2) ("c" . 1) ("b" . 2) ("b" . 1) ("a" . 2) ("a" . 1)) > (mycartesianproduct (list "a" "b") (list 2 1)) '(("a" . 2) ("a" . 1) ("b" . 2) ("b" . 1)) > (mycartesianproduct (list 1) (list "a")) '((1 . "a")) > (mycartesianproduct null (list "a" "b" "c")) '()
Notes:
 We ask you to name your function
mycartesianproduct
because Racket already provides a similar (but slightly different)cartesianproduct
function (which you cannot use, of course).  Use the
mapcons
function from above as a helper function in yourcartesianproduct
definition.  Racket’s
append
function is helpful here.
 We ask you to name your function

(8 points) Assume that the elements of a list are indexed starting with 0. Define a function
alts
that takes a listxs
and returns a twoelement list of lists, the first of which has all the evenindexed elements (in the same relative order as inxs
) and the second of which has all the oddindexed elements (in the same relative order as inxs
).> (alts (list 7 5 4 6 9 2 8 3)) '((7 4 9 8) (5 6 2 3)) > (alts (list 5 4 6 9 2 8 3)) '((5 6 2 3) (4 9 8)) > (alts (list 4 6 9 2 8 3)) '((4 9 8) (6 2 3)) > (alts (list 3)) '((3) ()) > (alts null) '(() ())
Notes:

As in all other problems, You should use the divide/conquer/glue strategy here. In particular, the solution for
(alts elts)
should be expressed in terms of combining(first elts)
with(alts (rest elts))
. 
You should not treat evenlength and oddlength cases differently, nor should you handle the singleton list specially.

You should use Racket’s
let
construct for declaring local names is helpful to avoiding unnecessarily recalculating the recursive call.


(10 points) Define a function
inserts
that takes a valuex
and an nelement listys
and returns an n+1element list of lists showing all ways to insert a single copy ofx
intoys
.> (inserts 3 (list 5 7 1)) '((3 5 7 1) (5 3 7 1) (5 7 3 1) (5 7 1 3)) > (inserts 3 (list 7 1)) '((3 7 1) (7 3 1) ( 7 1 3)) > (inserts 3 (list 1)) '((3 1) (1 3)) > (inserts 3 null) '((3)) > (inserts 3 (list 5 3 1)) '((3 5 3 1) (5 3 3 1) (5 3 3 1) (5 3 1 3))
Notes:
 The
mapcons
function from above is useful here.  Think very carefully about the base case and the combination function for the recursive case.
 The

(14 points) Define a function
mypermutations
that takes as its single argument a listxs
of distinct elements (i.e., no duplicates) and returns a list of all the permutations of the elements ofxs
. The order of the permutations does not matter.> (mypermutations null) '(()) > (mypermutations (list 4)) '((4)) > (mypermutations (list 3 4)) '((3 4) (4 3)) ; order doesn't matter > (mypermutations (list 2 3 4)) '((2 3 4) (3 2 4) (3 4 2) (2 4 3) (4 2 3) (4 3 2)) > (mypermutations (list 1 2 3 4)) '((1 2 3 4) (2 1 3 4) (2 3 1 4) (2 3 4 1) (1 3 2 4) (3 1 2 4) (3 2 1 4) (3 2 4 1) (1 3 4 2) (3 1 4 2) (3 4 1 2) (3 4 2 1) (1 2 4 3) (2 1 4 3) (2 4 1 3) (2 4 3 1) (1 4 2 3) (4 1 2 3) (4 2 1 3) (4 2 3 1) (1 4 3 2) (4 1 3 2) (4 3 1 2) (4 3 2 1))
Notes:
 We ask you to name your function
mypermutations
because Racket already provides the same function namedpermutations
(which you cannot use, of course).  In this problem, you are allowed to use one or more recursive helper functions.
 Although the specification allows the permuted elements to be listed in any order, the above examples show an order that works particularly well with the divide/conquer/glue strategy. In particular, study the above examples carefully to understand (1) the recursive nature of
mypermutations
and (2) why theinserts
function from above is helpful to use when definingmypermutations
.  In the example
(mypermutations (list 1 2 3 4))
, the 24 results would normally be printed by Racket in 24 separate lines, but here they have been formatted to strongly sugggest a particular solution strategy.
 We ask you to name your function
Extra Credit: Permutations in the Presence of Duplicates (15 points)
This problem is optional. You should only attempt it after completing all the other problems.
Define a version of the mypermutations
function named mypermutationsdup
that correctly handles lists with duplicate elements. That is, each permutation of such a list should only be listed once in the result. You should not generate duplicate permutations and then remove them; rather, you should just not generate any duplicates to begin with. As before, the order of the permutations does not matter.
> (mypermutationsdup (list 2 1 2))
'((1 2 2) (2 1 2) (2 2 1)) ; order doesn't matter
> (mypermutationsdup (list 1 2 1 2 2))
'((1 1 2 2 2) (1 2 1 2 2) (1 2 2 1 2) (1 2 2 2 1)
(2 1 1 2 2) (2 1 2 1 2) (2 1 2 2 1)
(2 2 1 1 2) (2 2 1 2 1) (2 2 2 1 1)) ; order doesn't matter