Hand in: please turn in a printout when you come to class, and also email your solution (as a plain text file!) to barak+cs351hw1@cs.nuim.ie

Teamwork: is encouraged! Please work in teams of up to two (2) people. Please just turn in one (1) solution set, with the entire team listed at the top, sorted by how much each person contributed. (The order will not affect grades; it will be used only for my own consistency checking of scores at the end of the course.)

Hints: Start early! Don't be afraid to ask for help! And, it is okay to define auxiliary functions to be shared by solutions to multiple problems.

NUIM/CS351 Assignment 1

Finger Exercises: Recursion and S-Expressions

1. Define find-path which takes two arguments, a target symbol and an s-expression, and returns false if the symbol does not occur anywhere in the s-expression however deeply nested, and returns a list of car and cdr symbols giving the location of the target symbol if it does. (If the target occurs multiple times, the path to any occurrence is okay.)

   Examples:

   	(find-path 'x '(a b (c d) (e (f g) h))) ; returns #f
   	(find-path 'x '(a b (c x) (e (f g) h))) ; returns (cdr cdr car cdr car)
   	(find-path 'x 'x)                       ; returns the empty list
   	(find-path 'foo '(foo bar foo))         ; returns either (car) or (cdr cdr car)
         

2. Define count-non-neg-nums which takes an s-expression and returns a count of the number of non-negative numbers which occur within it, no matter how deeply nested.

3. Define sum-even-nums which takes an s-expression and returns the numeric sum of all even numbers that occur within it.

4. Define count-foos-minus-bars which takes an s-expression and returns the number of times the foo symbol occurs within it minus the number of times the bar symbol occurs within it.

   Examples:

   	(count-non-neg-nums '(a b 11 (22) 33 c (-1 -1 -1 0 0 0) d e))      ; returns 6
   	(sum-even-nums '(a b (2 4) (7 7 7) (() (foo bar) -100)))           ; returns -94
   	(count-foos-minus-bars '(x x x foo (foo) (((((bar)) bar) foo) x))) ; returns 1
         

5. Define generalized-noah which takes a list and a positive integer and returns the list it was passed but with elements parcelled up into chunks of the given size, with any left over in their own chunk.

   Examples:

   	(generalized-noah '(a b c d e f g) 2)   ; returns ((a b) (c d) (e f) (g))
   	(generalized-noah '(a b c d e f g) 1)   ; returns ((a) (b) (c) (d) (e) (f) (g))
   	(generalized-noah '(a b c d e f g) 3)   ; returns ((a b c) (d e f) (g))
         

6. Define the higher-order function rep which takes a one-argument function and a non-negative integer, and returns a one-argument function which applies the passed function the given number of times.

   Examples:

   	((rep cdr 3) '(z y x w v u t s r q))     ; returns (w v u t s r q)
   	((rep sin 3) 1)                          ; returns 0.6784304773607402
   	((rep sin 0) 1)                          ; returns 1
   	((rep (rep (lambda (x) (+ x 1)) 3) 5) 0) ; returns 15