Problem Set: Recursive Functions I

Objectives

During this activity, students should be able to:

• Write simple recursive functions using the Clojure programming language.

This activity helps students develop the following skills, values and attitudes: ability to analyze and synthesize, capacity for identifying and solving problems, and efficient use of computer systems.

Activity Description

This activity can be developed individually or in pairs.

Solve the following programming problem set using Clojure. Place all your functions and unit tests in a file called recursion.clj. All problems should be solved using explicit recursion or the recur and loop special forms.

1. The function my-count returns the number of elements contained in its input list. Do not use the predefined count function. Unit tests:

   (deftest test-my-count
     (is (= 0 (my-count ())))
     (is (= 1 (my-count '(a))))
     (is (= 3 (my-count '(a b c)))))
   

2. The function add-list returns the sum of all the elements of its input list, or 0 if its empty. Assume that all the elements in the input list are numbers. Unit tests:

   (deftest test-add-list
     (is (= 0 (add-list ())))
     (is (= 10 (add-list '(2 4 1 3))))
     (is (= 55 (add-list '(1 2 3 4 5 6 7 8 9 10)))))
   

3. The function member? takes two arguments, any data x and a list lst. Returns true if x is contained in lst, false otherwise. Unit tests:

   (deftest test-member?
     (is (not (member? 'a ())))
     (is (member? 'a '(a b c)))
     (is (member? 'a '(c b a b c)))
     (is (not (member? 'x '(a b c)))))
   

4. The function list-of-symbols? takes a list lst as its argument. It returns true if all the elements (possibly zero) contained in lst are symbols, or false otherwise. Use the symbol? predicate to determine if something is a symbol. Unit tests:

   (deftest test-list-of-symbols?
     (is (list-of-symbols? ()))
     (is (list-of-symbols? '(a)))
     (is (list-of-symbols? '(a b c d e)))
     (is (not (list-of-symbols? '(a b c d 42 e))))
     (is (not (list-of-symbols? '(42 a b c)))))
   

5. The function my-last returns the last element of its input list, or nil of its empty. Do not use the predefined last function. Unit test:

   (deftest test-my-last
     (is (nil? (my-last ())))
     (is (= 'x (my-last '(x))))
     (is (= 'c (my-last '(a b c)))))
   

6. The function cons-end takes two arguments, any data x and a list lst. Returns a list composed by the same elements of lst but with x at the end. Unit tests:

   (deftest test-cons-end
     (is (= '(b c d a) (cons-end 'a '(b c d))))
     (is (= '(a) (cons-end 'a ()))))
   

7. The function my-reverse takes a list as an argument. It returns another list with the same elements as the input list, but in reverse order. Do not use the predefined reverse function. Unit test:

   (deftest test-my-reverse
     (is (= () (my-reverse ())))
     (is (= '(c b a) (my-reverse '(a b c))))
     (is (= '(3 (b c d) a) (my-reverse '(a (b c d) 3)))))
   

8. The function my-butlast returns a list with the same elements as its input list but excluding the last element, or nil of its empty. Do not use the predefined butlast function. Unit tests:

   (deftest test-my-butlast
     (is (nil? (my-butlast ())))
     (is (= () (my-butlast '(x))))
     (is (= '(a b) (my-butlast '(a b c)))))
   

9. The function my-concat returns the resulting list of appending the two lists it takes as input. Do not use the predefined concat function. Unit tests:

   (deftest test-my-concat
     (is (= '(a b c) (my-concat '(a b c) ())))
     (is (= '(1 2 3) (my-concat () '(1 2 3))))
     (is (= '(a b c 1 2 3) (my-concat '(a b c) '(1 2 3)))))
   

10. The function deep-reverse takes a list as its input. It returns a list with the same elements as its input but in reverse order. If there are any nested lists, these too should be reversed. Unit tests:

    (deftest test-deep-reverse
      (is (= () (deep-reverse ())))
      (is (= '(3 (d c b) a) (deep-reverse '(a (b c d) 3))))
      (is (= '(((6 5) 4) 3 (2 1)) (deep-reverse '((1 2) 3 (4 (5 6)))))))
    

Source of many of these problems: Ninety-Nine Lisp Problems

Deliverables

The program source file must include at the top the authors’ personal information (name and student id) within comments. For example:

;----------------------------------------------------------
; Activity: Problem Set: Recursive Functions I
; Date: August 24, 2017.
; Authors:
;          A01166611 Pepper Pots
;          A01160611 Anthony Stark
;----------------------------------------------------------

Also, each function should include a documentation string (docstring) with a brief description of its behavior. For example:

(defn max2
  "Returns the largest of the two numbers x and y."
  [x y]
  (if (> x y) x y))

Only one team member needs to upload the file.

Due date is Thursday, August 24.

Evaluation

This activity will be evaluated using the following criteria:

-10	The program doesn't contain within comments the author's personal information.
-30	A docstring is missing in one or more functions.
10	The program contains syntax errors.
1	The program was plagiarized in whole or in part.
10-100	Depending on the amount of exercises that were solved correctly.