# Scheme代写Dr.Racket | CMPSC 461 Project 2

Programming Languages Concepts

CMPSC 461

Project 2

Due August 5, 2019 at 11:59 pm

Instructions:

Download Dr. Racket and use it to complete the following programming exercises.

NOTE: You can ONLY use primitive functions covered in module 10 such as: append, pair, cons, null, car, cdr, map, eval, display, write, read, input, set! begin, cond, if, else, member, all predicates covered (eq?, eqv?…..), let, let*, letrec, symbol, define, lambda, length, list, quote (if there is any other functions that was covered in the lectures and is missing here, please let me know. You can write extra helper functions if you need to. If you use functions not covered in the modules, you will earn a 0 on the entire project and will be subject to plagiarism. Please refer to the syllabus for more details.

Rubrics: as shown on Canvas

Problems: Use Racket language to answer the following questions.

• Write a function smooth that levels a nested list and returns only one simple list (not nested). A sample run is as follows:

(smooth ‘(a (b) ((c (d)) e))) should return (a b c d e)

• Implement a function to satisfy a predicate

Write a Scheme function that returns a list containing all elements of a given list that satisfy a given premise. For example, (fun (lambda (a) (< a 10)) ‘(1 2 12 14 15)) should return (1 2).

• Write a function multiply that multiplies two lists. You need to test your function on various lists, where lists may be empty, simple or nested lists.

For example:

1. (multiply ‘() ‘(4 5)) returns ()

ii.(multiply ‘(1 2) ‘(3 4)) returns ((1 . 3) (1 . 4)(2 . 4) (2 . 3)) (Note that your printout order may be different than mine)

iii.(multiply ‘(1 (10 2)) ‘(4 5)) returns

(((10 2) . 5) ((10 2) . 4) (1 . 5) (1 . 4))

• Define a Scheme function called overlap that takes two sorted lists of numbers as arguments and that returns a list of the values in common between the two lists. For example:

(overlap ‘(1 2 2 3 3 4 7 7 7) ‘(1 2 2 2 2 3 5 7 8))

(1 2 2 3 7)

You may assume that your function is passed two simple lists, that they contain only numbers, and that the numbers appear in sorted (nondecreasing) order.  But as in the example above, they might contain duplicates.  Any given number from a list can match at most once.  Thus, the two occurrences of 2 in the first list can match 2 of the occurrences of 2 in the second list, but the additional occurrences of 2 in the second list do not appear in the result because they aren’t matched.  Similarly, the result includes only one 7 even though the first list has three occurrences of 7 because the second list has only 1 such occurrence.

### 5-    Implement list-tail and list-ref

Your list-tail and list-ref functions should take two operands, where the first operand must be a list, and the second operand must be an int.

(list-tail <list> <k>)
(list-ref <list> <k>)

It is an error if <list> has fewer than <k> elements.

list-tail should return the sublist of <list> obtained by omitting the first <k> elements.

list-ref should return the kth element of list. (This is the same as the car of (list-tail <list> <k>)). List-ref gives us an indexing operator like operator[] in C++.

For example:

> (list-tail ‘(a b c d e) 2)
(c d e)
> (list-ref ‘(a b c d e) 2)
c

• Implement assoc

The idea of an alist (for “association list”) is fundamental to Scheme/LISP, and is the simplest possible implementation of a dictionary ADT built out of simple cons lists (c.f. map in C++ STL). An alist must be a list of cons pairs, for instance:

> (define e ‘((a 1) (b 2) (c 3)))

The Standard Library procedure assoc has the following form:

(assoc <obj> <alist>)

It finds the first pair in <alist> whose car field is <obj>, and returns that pair. If no pair in <alist> has <obj> as its car, then 0 (not the empty list) is returned.

Note that assoc is required to use equal? to compare <obj> with the items in <alist>.

For example:

> (assoc ‘a e)
(a 1)
> (assoc ‘b e)
(b 2)
> (assoc ‘d e)
0
> (assoc (list ‘a) ‘(((a)) ((b)) ((c))))
((a))
> (assoc 5 ‘((2 3) (5 7) (11 13)))
(5 7)

Honor code: I pledge on my honor that I have not given or received any inappropriate help on this assignment” E-mail: [email protected]  微信:itcsdx 