Question

Consider the following Scheme function foo:

(define (foo x)
  (cond
    ((null? x) 0)
    ((not (list? (car x)))
     (cond
       ((eq? x '()) (foo (car x)))
       (else (+ 1 (foo (cdr x))))))
    (else (+ (foo (car x)) (foo (cdr x))))))

1. (8 pts)

   Explain what the function computes and how. Don’t just restate the function definition in English — explain the algorithm. Hint: not all the code in this function does something useful.

2. (2 pts)

   Show the result of executing the expression

   (foo '(((a (b c) d) (((d) e) f) g)))

Answer 1

a)

Function computes total number of atoms in a nested list.

Let's number each line of the program.

1.(define (foo x)
2. (cond
3.   ((null? x) 0)
4.   ((not (list? (car x)))
5.    (cond
6.       ((eq? x '()) (foo (car x)))
7.       (else (+ 1 (foo (cdr x))))))
8.   (else (+ (foo (car x)) (foo (cdr x))))))

Algorithm works in the following manner:

I) If x is empty list it returns 0 (3rd line of program)

ii) Line 4: if first element of given list is not a list then it will execute line 6 of the program which checks for x is null. But we have already checked x is null or not at line number 3. So line number 6 of the code is not at all useful. So go directly to the line number 6 else condition. It counts that atom and recursively passes rest of the list to foo.

iii) Line 4: if first element of given list is list then it will execute line number 8 and passes 1st element of list which itself is a list to foo function to count number of atoms in it and also passes rest of the elements of list to foo function by another function call recursively. And then adds both function returns and returns total count of the atoms.

• If it is atom count it and recursively pass rest of the elements to foo function. Line number 4 - 7 of the program doing this part.
• If it is a list recursively pass the list to foo function and add total count (Line number 8)
• Line number 6 of the program is not useful.

b)

Given expression :(foo '(((a (b c) d) (((d) e) f) g)))

atoms in the nested list are : a , b, c, d, d, e, f, g

Total number of atoms = 8.

Therefore, Result of the expression is 8.