virtuallyalike
virtuallyalike

Reputation: 5

SCHEME program explanation

Studying for a test, and this is a practice problem:

What does the following Scheme function do? You must explain each block/case of the codes and provide two test cases.

(define (x lis)
 (cond
   ((null? lis) 0)
   ((not (list? (car lis)))
    (cond
      ((eqv? (car lis) 3)(x (cdr lis)))
      (else (+ 1 (x (cdr lis))))))
   (else (+ (x (car lis)) (x (cdr lis))))
 )
)

Could someone break down this code?

Upvotes: 0

Views: 123

Answers (1)

Martin Půda
Martin Půda

Reputation: 7576

First of all, I rewrote this code to more readable form (and I also replaced inner cond with if, meaning of code won't change):

(define (x lis)
  (cond
    ((null? lis) 0)
    ((not (list? (car lis)))
     (if
      (eqv? (car lis) 3)
      (x (cdr lis))
      (+ 1 (x (cdr lis)))))
    (else (+ (x (car lis))
             (x (cdr lis))))))

And now, I will break this line by line:

  • cond with three clauses null?, list? (car ...), else - you're going through given list, doing something with each element
  • ((null? lis) 0): zero is neutral element for addition, so result of this function will be number and you're summing something
  • ((not (list? (car lis))): when car is "atom"...
  • (eqv? (car lis) 3)
  • ... and it's 3, call this function with (cdr lis) = ignore this element
  • ... and it isn't 3, call this function with (cdr lis), but add 1 to result
  • (+ (x (car lis)) (x (cdr lis))) else sum result of this function called on car and result of this function called on cdr (this is common pattern for functions, which work with nested lists, for example flatten)

So, what does this function do? It returns count of elements in given list, that are different from 3, and given list can be nested.

See examples:

> (x '(1 2 3 4 5))
4

There's five elements in list, but one is eqv? to 3, so you don't count it.

> (x '(3 3 3))
0

Three elements in list, but every is eqv? to 3, so you skip them all.

> (x '(1 2 (3 4) (5 6 (7))))
6

Seven elements in this nested list, but one is eqv? to 3, so you count only six.

Upvotes: 2

Related Questions