ASSIGNMENT 3 (SCHEME) SOlution

Scheme Functions







Weight: Assignment 3 will count for 5% of your course grade.




This assignment is to be your own work. Refer to the course academic integrity statement in the syllabus.




This homework provides some practice in Scheme programming. The Racket environment, which can be downloaded from http://racket­lang.org is friendly scheme imple can be installed on most operating systems (e.g., Mac, Linux, Unix, Windows). On Windows, get the installer from the racket­lang website. For linux systems you can a racket package in your distribution's package manager. After installing use the drracket command to start up the IDE. Be sure to select R5RS as the language on language menu. You should only have to do this once after installing.




You can edit your code in the upper panel of the Racket IDE and save it from there. Or edit in any text editor and load it into Racket.




Turning in your assignment




Turn in a plain text file named HW3.scm containing legal scheme code ­­ you should be able to take the contents of your file and run it through racket without errors. C own test cases for each function: you may include the test cases in what you turn in. To submit your assignment, turn in your file by uploading on the Assignment3 (Sc DROPBOX on Blackboard (under AssignmentSubmisions menu). Be sure to include your name as a comment at the top of the file. You may turn in your assignment u Only the last one submitted will be graded. Please let the instructor know if you need to resubmit it a 6th time.




The work you turn in is to be your own personal work. You may not copy another student's code or work together on writing code. You may not copy code from the anything else that lets you avoid solving the problems for yourself.




Grading




The assignment will be marked for correctness and effective programming. You will lose points if you don't (1) provide test functions, (2) explain your code with approp comments, and (3) follow a good programming style.




General rules




Unless directed otherwise, you should implement your functions using recursive definitions that you build up from the basic built­in functions such as cons, car, cd etc.




Don't use set! and don't define anything except functions.




Problems




1. (deepCount L) (15%)




The function deepCount takes a single argument, L, a list, and returns how many elements (atoms) are contained in L and the sublists in L.




Example:




(deepCount '(1 (2 3 4) (5) 6 7 (8 9) "10" 11)) = 11




(Note: The lenght function covered in class calculated a shallow count of elements (i.e., only number of elements in L without looking into sublists). deepCount should into sublists and count the elements in each sublist.)




(HINT: The predicate function (pair? L) return true if L is a pair value (such as a list))







2. (nthElement n L) (10%)




The function nthElement takes an index value n and a list L and returns the nth element of the list L (0­based indexing). Assume that the index, n, is at least 0 and s the length of the list. ( i.e., you do not have to worry about error cases such as when n is negative or too large.)




Example:




(nthElement 3 '(1 2 3 4 (5) "6")) = 4




(nthElement 4 '(1 2 3 4 (5) "6")) = (5)




(HINT: The trick with problems like this is to reduce both the size of the list and the size of the integer argument in recursive calls. The 3rd element of a list is the 2nd e the cdr of the list.)




3. (repL n v L) (10%)




http://www.eecs.wsu.edu/~arslanay/CptS355/assignments/Scheme_Assignment.html 1/3
12/11/2016 CptS 355 - Assignment 3 - Scheme




The function repL takes an index value n, a value v, and a list L and returns a (new) list which is the same as L, except that the nth element is v. Again assume 0­bas Assume that the index, n, is at least 0 and smaller than the length of the list.




Example:




(repL 3 40 '(1 2 3 4 (5) "6")) = (1 2 3 40 (5) "6")




(repL 4 5 '(1 2 3 4 (5) "6")) = (1 2 3 4 5 "6")







4. (range min step max) (15%)




The function range takes a starting index min, a step value step, and a max index max and returns a list of integers (min min+step min+step+step ... max+k* where k is the largest integer such that min+k*step<max and min+(k+1)*stepmax. If min ≥ max and step ≥ 0 OR min<max and step<0 , return the empty list.




Example:




(range 0 5 30) = (0 5 10 15 20 25)




(range 5 ­1 0) = (5 4 3 2 1)







5. (merge2 L1 L2) (10%)




The function merge2 takes two lists of integers, L1 and L2, each already in ascending order, and returns a merged list that is also in ascending order. The length of th the sum of the lengths of the original lists.




Examples:




(merge2 '(4 6 7) '(3 5 7)) = (3 4 5 6 7 7)




(merge2 '(1 7) '(2 5 7)) = (1 2 5 7 7)




(merge2 '() '(3 5 7)) = (3 5 7)







(fold L)




Just use the definition given in class. You'll need it for the function below.







6. (mergeN Ln) (15%)




Using merge2 function defined above and the fold function, define mergeN which takes a list of lists, each already in ascending order, and returns a new list containi elements in ascending order.




(Provide an answer using fold; without using recursion).




Example:




(mergeN '()) = ()




(mergeN '((2 4 6) (1 4 5 6))) = (1 2 4 4 5 6 6)




(mergeN '((2 4 6 10) (1 3 6) (8 9))) = (1 2 3 4 6 6 8 9 10)




Note that this requires making sure that your understanding of fold encompasses seeing that it can return a list, not just a simple value; but the solution is, in fact, a ve use of fold once you choose the right value for the base case corresponding to the empty list as input.




In a comment, discuss the question of how many cons operations your function uses to produce its result, in terms of the sizes of the input lists. Explain your answer. problem, I suggest looking first at how many cons operations are used by merge2 for lists of length len1 and len2. If mergeN is used for a single list, what is the answe lists? For n lists?




7. (matrixMap f M) (10%)




A matrix M can be represnted in Scheme as a list of lists, for example M='((1 2) (3 4))




Without using recursion, write a function matrixMap, which takes a function f and a matrix M as arguments and returns a matrix consisting of f applied to the element




Example:




(matrixMap (lambda (x) (* x x)) '((1 2) (3 4)) ) = ((1 4) (9 16))




(matrixMap (lambda (x) (+ 1 x)) '((0 1 2) (3 4 5)) ) = ((1 2 3) (4 5 6))







8. (avgOdd L) (15%)




Without using recursion, write a function avgOdd which takes a list L and returns the average of the odd values in L.




Example:




(avgOdd '(1 2 3 4 5)) = 3




Use (odd? n) and (even? n) predicate functions to check if a given number n is odd or even.