Assignment 3: Scheme
Write all your solution code in a single file named a3.scm. Make sure to use exactly the same function names and arguments (otherwise the marking software will give you 0!). Please use MIT Scheme.
You can (and probably should!) create helper functions for some of the questions.
Some of the questions ask you to write your own version of built-in Scheme functions. Of course, don’t just use the built-in version in your answer. Implement everything yourself using basic Scheme functions and recursion.
You don’t need to do much error checking: you can assume that valid data is passed to the functions you write.
Questions
(2 marks) Write a function called (my-last lst) that returns the last element of lst. For example:
> (my-last ‘(cat))
;Value: cat
> (my-last ‘(cat dog))
;Value: dog
> (my-last ‘(cat dog (1 2 3)))
;Value 11: (1 2 3)
> (my-last ‘())
;my-last: empty list
Notice that calling my-last on an empty prints the error message “my-last: empty list”. To do this, evaluate (error “my-last: empty list”).
MIT Scheme has a built-in function called last that does that same thing as my-last. Of course, don’t use last in your implementation of my-last! Implement it using recursion and basic Scheme functions.
(2 marks) Write a function called (snoc x lst) that returns a list that is the same as lst except x has been added to the right end of the list. For example:
> (snoc ‘a ‘(1 2 3))
;Value: (1 2 3 a)
> (snoc ‘(1 2 3) ‘(1 2 3))
;Value: (1 2 3 (1 2 3))
(2 marks) Write a function called (range n) that returns the list (0 1 2 … n-1). You can assume n is an integer, and if it is 0, or less, return the empty list. For example:
> (range 4)
;Value 22: (0 1 2 3)
> (range 9)
;Value 23: (0 1 2 3 4 5 6 7 8)
> (range 0)
;Value: ()
> (range -3)
;Value: ()
MIT Scheme has a built-in function called iota that does that same thing as range. Of course, don’t use iota in your implementation of range! Implement it using recursion and basic Scheme functions.
(2 marks) Write the function called (deep-sum lst) that returns the sum of all the numbers in lst, including numbers within lists. Non-numbers should be ignored. For example:
> (deep-sum ‘(a 2 (b (1 c)) 3))
;Value: 6
You can assume lst is always a list. Return 0 if lst has no numbers.
Use number? to test for numbers, and list? to test for lists.
(2 marks) Write a function called (count-primes n) that returns the number of primes less than, or equal to, n. For example:
> (count-primes -10)
;Value: 0
> (count-primes 0)
;Value: 0
> (count-primes 10)
;Value: 4
> (count-primes 100)
;Value: 25
> (count-primes 1000)
;Value: 168
> (count-primes 10000)
;Value: 1229
While you should try to make count-primes reasonably efficient, the point of this question is to learn basic Scheme programming. So, while calling (count-primes 1000) should return its answer nearly instantaneously, it’s okay if (count-primes 10000) takes, say, a few seconds to run.
(1 mark) Write a function called (is-bit? x) that returns #t when x is the number 0 or 1, and #f otherwise.
For example:
> (is-bit? 0)
;Value: #t
> (is-bit? 1)
;Value: #t
> (is-bit? 2)
;Value: #f
> (is-bit? ‘cow)
;Value: #f
> (is-bit? ‘(0 1))
;Value: #f
Notice that #f is returned for every input that is not either 0 or 1, even when the input is not a number.
(1 mark) Write a function called (is-bit-seq? lst) that returns true if lst is the empty list, or if it contains only bits (as defined by is-bit?). You can assume that lst is a list.
Note: MIT Scheme has a special built-in syntax, and some special functions, for bit strings. Don’t use any of those for these questions!
(3 marks) Write a function called (all-bit-seqs n) that returns a list of all the bit sequences of length n. The order of the sequences doesn’t matter. If n is less than 1, then return an empty list. You can assume that n is an integer.
For example:
> (all-bit-seqs 0)
;Value: ()
> (all-bit-seqs 1)
;Value 14: ((0) (1))
> (all-bit-seqs 2)
;Value 15: ((0 0) (0 1) (1 0) (1 1))
> (all-bit-seqs 3)
;Value 16: ((0 0 0) (0 0 1) (0 1 0) (0 1 1)
(1 0 0) (1 0 1) (1 1 0) (1 1 1))
Your algorithm must work, at least in theory, for any value of n.