Principles of Programming Languages — Homework 3

Due by class time Friday, September 17

Reading

Exercises

For these problems, think recursively, and be sure to test your functions on at least the examples shown. Remember:

  1. For the base case, solve the simplest possible version of the problem directly. The solution to the base case should be obvious, with no thinking required.
  2. For the general case, make the problem slightly simpler, and then let the recursion solve the simpler version of the problem for you.
  3. Use the result of the recursion in step 2 to help you construct a solution to the original problem.

  1. Write the function (addup-nums ls), which takes a list ls and adds up all of the numbers in the list, ignoring any symbols. Examples:

      (addup-nums '())  →  0
  (addup-nums '(1 a 2 b 3 c 4 d 5 e))  →  15
  (addup-nums '(apple 40 30 20 10)) → 100
  (addup-nums '(w x y z)) → 0
  (addup-nums '(2 4 6 8)) → 20

  2. Write the function (laugh n), which takes a number n and constructs a list containing n ha symbols. Examples:

      (laugh 0)  →  ()
  (laugh 4)  →  (ha ha ha ha)
  (laugh 1)  →  (ha)

  3. Write the function (copies n x), which takes a number n and an item x and constructs a list containing n copies of x. Examples:

      (copies 4 'practice)  →  (practice practice practice practice)
  (copies 3 '(heh))  →  ((heh) (heh) (heh))
  (copies 1 42)  →  (42)
  (copies 0 'whatever)  →  ()

  4. Write the function (times-ten nums), which takes a list of numbers and returns a new list with each number multiplied by 10. Examples:

      (times-ten '(1 2 3 4 5))  →  (10 20 30 40 50)
  (times-ten '(25))  →  (250)

  5. Write the function (flip ls), which takes a list ls and returns a new list with the elements in reverse order. You are not allowed to use Scheme's built-in reverse function for this problem, but you may define and use snoc as a helper function. Examples:

      (flip '())  →  ()
  (flip '(a b c d e f g))  →  (g f e d c b a)

  6. Write the function (concat ls1 ls2), which takes two lists ls1 and ls2 and returns the concatenation of the lists, namely a new list containing all of the elements of ls1 followed by all of the elements of ls2, in their original order. You are not allowed to use Scheme's built-in append function for this problem. Examples:

      (concat '() '(w x y z))  →  (w x y z)
  (concat '(a b c d) '())  →  (a b c d)
  (concat '(a b c d) '(w x y z))  →  (a b c d w x y z)
  (concat '(1 2 3) '(four five six seven)) → (1 2 3 four five six seven)

  7. Write the function (biggest nums), which takes a non-empty list of numbers and returns the biggest number in the list. Hint: if the list has only one element, then just return that element. Otherwise, if the first element is bigger than the biggest remaining element, return the first element. If not, return the biggest remaining element. Examples:

      (biggest '(9 1 5 3 2 2 7 1 4))  →  9
  (biggest '(6 0 4 3 12 1 9))  →  12
  (biggest '(5))  →  5

Turning in Your Homework