Question 1
In a file called a3q1_composition.scm solve the following problems.
• Function composition f ∘ g is an operation that takes two functions f and g and returns a function h such that h(x) = f(g(x)).
[2 marks] Define a function (compose f g) that returns a composed function f ∘ g, such that the following usage works as shown.
• (define square (lambda(x)(* x x)))
• (define double (lambda(x)(+ x x)))
• ((compose square double) 3) → 6^2 = 36
• [2 marks] Define a function (endswith x) that takes an integer argument in the range [0,9] and returns a predicate function. The returned predicate should accept an integer y and return true if the last digit in y matches the given digit x.
E.g.,
• ((endsWith 0) 17) → #f
• ((endsWith 3) 1213) → #t
• [3 marks] Define a function called (newmap f) that takes a function f as argument and returns a function. The returned function should take a list as argument and map the function f over each element of the list. You should not use the built-in map function in your solution.
E.g.
• (define double-mapper (newmap (lambda(x)(* x 2))))
• (double-mapper ‘(1 2 3 4)) → (2 4 6 8)
• (double-mapper ‘(10 20 30)) → (20 40 60)
• [4 marks] Define a function called (newfilter keep? f) that takes a boolean keep? and predicate function f as arguments and returns a function. That returned function should take a list as argument and perform a modified filter of the elements in the list using the predicate f, and either returning the elements that pass the predicate if keep? is true, or discards them (and only them) if keep? is false.
E.g.
• (define bigNums (newfilter #t (lambda(x)(> x 25))))
• (define smallNums (newfilter #f (lambda(x)(> x 25))))
•
• (bigNums ‘(10 20 30 40 50)) → (30 40 50)
• (smallNums ‘(10 20 30 40 50)) → (10 20)
• [2 marks] Using the functions you created above (and given the range function from lecture), fill in the blank () on the statement below so that the definition of the function myfunc produces the expected results as shown.
• (define myfunc )
• (myfunc (range 0 10)) → (3 6 9 12 15 18 21 24 27)
Question 2
In a file called a3q2_lists.scm solve the following problems.
• [3 marks] Create a procedure mean that takes any list as argument and returns the arithmetic mean of just the elements that are numbers, ignoring all other elements. The procedure should return 0 if there are no numbers.
E.g.,
• (mean ‘(1 2 3 4 5)) → 3
• (mean ‘(1 a 2 b c d e 3)) → 2
• [4 marks] Create a procedure called slice that takes a list and two integer indices as arguments and returns a sublist of the input list between the indices start (inclusive) and end (exclusive). If the given indices are out of bounds, then the returned sublist should include any existing values in the given ranges.
E.g.,
• (slice ‘(0 1 2 3 4 5 6 7 8 9) 3 8) → (3 4 5 6 7)
• (slice ‘(0 1 2 3 4 5 6 7 8 9) 5 25) → (5 6 7 8 9)
• (slice ‘(0 1 2 3 4 5) -10 3) → (0 1 2)
• [5 marks] Create a procedure called preceeding that will take a list of numbers as argument and determine the elements and indices of those elements that preceed a negative number in the given list. The returned information should be in the form of a pair of lists: ((values) . (indices)).
E.g.,
• (preceeding ‘(1 -2 3 4 -5 6 -7 -8)) → ((1 4 6 -7).(0 3 5 6)) ;note: drracket will display this as ((1 4 6 -7) 0 3 5 6)
• [5 marks] Create a procedure (tails L) that returns a list of lists according to the following rule: The first sublist should be all of the items that follow the largest item in the input list, the second sublist should be all of the items that follow the largest item in the first sublist, and so on until no items remain. If there is a tie for the largest item, select the largest element that is closest to the front of the list. You may assume the input list contains only numbers.
E.g.,
• (tails ‘(3 6 8 9 7 4 8 6 3)) → ((7 4 8 6 3) (6 3) (3) ())
• (tails ‘(4 2 8 7 8 1 2)) → ((7 8 1 2) (1 2) ())
Question 3
In a file called a3q3_trees.scm solve the following problems.
• [3 marks] Create a procedure called tree-filter for trees that is analogous to the built-in filter for flat lists (see Section 4.4). This function should apply a predicate to every element of the tree, keeping only those that pass, and return the results in a tree of the same shape as the original.
E.g.:
• (tree-filter even? ‘(1 (2 3) ((4 5) (6 7)) (((8 (9)))))) → ((2) ((4) (6)) (((8 ()))))
• [3 marks] Create a procedure called height that takes as argument an arbitrarily deeply nested list (ie a tree) and returns the maximum depth of any item in any of its sublists; the depth of an object in a list is the number of cars that can be applied to it (not necessarily in a row).
E.g.:
• (height ‘a) → 0
• (height ‘(a)) → 1
• (height ‘(a (b) c)) → 2
• (height ‘(((((a(((b))))))))) → 8
• [3 marks] Create a procedure called flattenList that takes a tree as an argument and returns a list of the leaf values of the tree.
E.g.:
• (flattenList ‘(1 (2 3) ((4 5 6 (7)))(((8 (9)))))) → (1 2 3 4 5 6 7 8 9)
• [6 marks] Create a procedure called squish that takes a tree as argument and returns a tree in which any two adjacent sublists have been merged into one sublist.
E.g.,
• (squish ‘((a) (b) c (d))) → ((a b) c (d))
• (squish ‘((1 2)(3) 4 (5 (6)(7))((8) 9))) → ((1 2 3) 4 (5 (6 7 8) 9))
Question 4
In a file called a3q4_streams.scm solve the following problems.
• [2 marks] Create a procedure (list->stream lis) that makes a stream from a given list.
• [3 marks] Create a procedure (stream->list strm n) that makes a list from the first n items of the given stream.
• [1 mark] Create a procedure (odds) that returns an infinite stream of all odd numbers starting from 1.
• [1 mark] Create a procedure (repeated x) that returns an infinite stream of the given value x.
• [3 marks] Create a procedure (stream-until strm pred) that counts the number of elements in a stream before the given predicate function pred evaluates to true. If the stream is exhausted before the predicate evaluates true, then return -1.
E.g.,
• (stream-until positive-integers (lambda(x)(>= x 15))) → 14
• (stream-until (repeated 7) (lambda(x)(> x 6))) → 0
• [3 marks] Create a procedure (loan amnt rate payment) that takes a principal loan amount, monthly interest rate, and fixed monthly payment as arguments and returns a stream representing the remaining balance of the loan on a monthly schedule.
E.g., a $10000 loan with 2.5% monthly interest with $500 monthly payments would be calculated as follows:
• $10000
• (10000-500)+(10000*0.025) = $9750
• (9750-500)+(9750*0.025) = $9493.75
• etc…
Note: the stream should terminate with the final value 0 if the balance ever fully paid.
(stream->list (loan 10000 0.025 500) 5) → (10000 9750.0 9493.75 9231.09375 8961.87109375)
(stream->list (loan 20 0.003 10) 5) → (20 10.06 0.09 0)
Bonus: [1 mark] Modify the procedure to round all values to two decimal places.
• [1 mark] Using your solutions to the previous problems, determine how many months it will take to pay off a loan of $250,000 with 0.15% monthly interest, and $2000 monthly payments.
Documentation & Testing
Documentation
• Ensure that your name and student number are in comments at the top of all files.
• Document the purpose of each function including its expected inputs (parameters) and output (return).
• Ensure that your code is well-formatted and easily readable; a happy TA is a generous TA.
• Please note, copying and pasting the assignment guidelines does not constitute sufficient documentation, and will receive zero marks.
• You may use any code or text found in lecture or the assignment but you must cite the source correctly.
Testing
• You are required to include testing runs of every function in your submission.
• The specific tests required depend on the question at hand, but should cover all valid inputs and all possible branches of your code.
• Unless otherwise specified, you may assume inputs supplied are of the correct type.
• Fabricated test outputs will result in 0 marks for a question.
• Your test cases are expected to be unique where appropriate
• Please note, copying and pasting the provided example runs does not constitute sufficient testing, and will receive zero marks.
• For best practices: Comment your testing as to what you are testing and why, giving expected output as well as observed output and explanations for any differences.
[10 marks total]
An example submission including documentation and testing can be found here: primes.scm.
A similar example demonstrating unit testing (borrowed from Racket) can be found here: primes.scm.
You are free to use either approach (or find your own).