Description
Write Scheme definitions for the following functions and convert them to continuation passing style (CPS). The continuation argument should be the last argument. For example, if you were asked to write factorial and its CPS counterpart, the answer would be:
(define factorial (lambda (n) (if (zero? n) 1 (* n (factorial (- n 1))))))
(define factorial-cps (lambda (n k) (if (zero? n) (k 1) (factorial-cps (- n 1) (lambda (v) (k (* n v)))))))
You do not have to convert simple scheme built-in functions like null?, eq?, list?, number?, car, cons, cdr to CPS, but all other helper functions you create should be in CPS.
1. A function duplicate that takes two argument, an element and a size, and creates a list of the requested size:
(duplicate 3 0) ==> ‘()
(duplicate 3 1) ==> ‘(3)
(duplicate 3 2) ==> ‘(3 3)
(duplicate 3 5) ==> ‘(3 3 3 3 3)
2. A function removedups that takes a list and removes any atom that is a repeat of the atom that immediately precedes it.
(removedups ‘()) ==> ‘()
(removedups ‘(a b c d d e f)) ==> ‘(a b c d e f)
(removedups ‘(a a b a a a c c a a a a d d d)) ==> ‘(a b a c a d)
3. The function count* that takes a list and and an element and returns the number of occurrences of the element in the list and all its sublists.
(count* ‘a ‘(b a (v a x) ((a) b a c))) ==> 4
4. The function numbersonly? that takes a list and returns if the list contains only numbers.
(numbersonly? ‘()) ==> #t
(numbersonly? ‘(1 3 5 7 3 4 10 34)) ==> #t
(numbersonly? ‘(1 2 4 a b f 3)) ==> #f
(numbersonly? ‘(1 2 (3 4))) ==> #f
5. The function cleannumbers that takes a list of lists and returns a list that contains only those sublists that contain only numbers.
(cleannumbers ‘((1 2 3) (a b) () (4 2 (3 4)) (3 5 1))) ==> ‘((1 2 3) () (3 5 1))
6. The function merge that merges two sorted lists of numbers into a larger sorted list.
(merge ‘() ‘(1 2 3)) ==> ‘(1 2 3)
(merge ‘(1 2 3) ‘()) ==> ‘(1 2 3)
(merge ‘(1 3 5 7 8 9 10) ‘(2 4 6)) ==> ‘(1 2 3 4 5 6 7 8 9 10)
7. The function evens that takes a boolean and a list. If the boolean is true, evens will return every element at an even index, and if the boolean is false, evens will return every element at an odd index.
(evens #t ‘()) ==> ‘()
(evens #t ‘(1)) ==> ‘()
(evens #f ‘(1)) ==> ‘(1)
(evens #t ‘(1 2 3 4 5 6 7 8 9)) ==> ‘(2 4 6 8)
(evens #f ‘(1 2 3 4 5 6 7 8 9)) ==> ‘(1 3 5 7 9)
8. The function Mergesort that takes a list of numbers and returns a sorted version. If you recall the merge sort algorithm, you call evens twice to get lists containing the elements and the even and odd indices, you then recursively call mergesort on each sublist, and then you call merge on the two lists returned by the recursive calls to mergesort.
(Mergesort ‘()) ==> ‘()
(Mergesort ‘(8 1 3 9 6 5 7 2 4 10)) ==> ‘(1 2 3 4 5 6 7 8 9 10)
9. Use continuation passing style to create the following function without using external helper functions and without adding new parameters. The function split takes a list and returns a list containing two sublists, the first with the elements at the even indices and the second with the elements at the odd indices:
(split ‘()) ==> ‘(()())
(split ‘(1)) ==> ‘(()(1))
(split ‘(1 2 3 4 5)) ==> ‘((2 4) (1 3 5))
10. Write the following function without external helper functions or additional parameters. You do not need to use continuation passing style, but you may use continuations or call-with-current-continuation to assist you. The function suffix takes an atom and a list and returns a list containing all elements that occur after the last occurrence of the atom.
(suffix ‘x ‘(a b c)) ==> (a b c)
(suffix ‘x ‘(a b x c d x e f)) ==> (e f)
