CODEWITHSUNDEEP
functional-programmingscheme
Philip DiSarro
Philip DiSarro

Reputation: 1025

How does recursively iterating through lists with CDR work with Cons in Scheme?

Specifically, I have the following function

(define (even-odd-filter x . intlist)   
  (if (equal? '() intlist)
      '()
      (if (equal? (modulo x 2) (modulo (car intlist) 2))
          (cons (car intlist) (even-odd-filter x (cdr intlist)))
          (even-odd-filter x (cdr intlist)))))

Can someone please explain why this would break on the second iteration? As far as I know, (car list) is meant to refer to the first element of list, however, in the second recursive call

(modulo (car int list) 2)

causes an error as the interpreter believes that (car intlist) references the whole list as opposed to the first element of said list.

I am quite lost on this, and any help would be appreciated.

Upvotes: 0

Views: 134

Answers (2)

Sylwester
Sylwester

Reputation: 48765

The reason why is that if you call (even-odd-filter 5 1 2 3) it will do (cons 1 (even-odd-filter 5 '(2 3))) and intlist will be ((2 3)) in the second iteration.

To avoid this it's best to use a helper such that only the outer call has rest arguments: 

(define (even-odd-filter x . intlist)
  (let helper ((intlist intlist))   
    (cond
      ((null? intlist) '())
      ((equal? (modulo x 2) (modulo (car intlist) 2))
       (cons (car intlist) (helper (cdr intlist))))
      (else
       (helper (cdr intlist))))))

Another nice thing with this is that x, that doesn't change in he iteration isn't passed but used as a free variable. It makes easier to read code. Since you have nested if I turned it into cond which is for a typical if-then-else scenario.

If you really want rest arguments in recursion, you need to use apply in each recursive call. This is not very efficient since it most likely will create a new list each iteration:

(define (even-odd-filter x . intlist)   
  (if (equal? '() intlist)
      '()
      (if (equal? (modulo x 2) (modulo (car intlist) 2))
          (cons (car intlist) (apply even-odd-filter x (cdr intlist)))
          (apply even-odd-filter x (cdr intlist)))))

Upvotes: 1

Renzo
Renzo

Reputation: 27434

The reason is that if you define a function with the syntax:

(define (function arg1 . rest-of-args-as-list) body)

you should call it always with a certain number of arguments, but not with a list. For instance, assuming you need to operate on a sequence of integers, you can call it in this way:

(function 1 2 3 4 5)

and inside the body of the function arg1 will be bound to 1 and rest-of-args-as-list will be bound to the list (2 3 4 5).

So in you case, if you call the function: (even-odd-filter 1 2 3 4 5), x will be bound to 1, intlist to (2 3 4 5) and in the second iteration, the function will be called as: (even-odd-filter 1 (3 4 5)) (since x is 1 and cdr of (2 3 4 5) is (3 4 5)). And calling it in this way will produce the error (in DrRacket):

modulo: contract violation
  expected: integer?
  given: '(3 4 5)
  argument position: 1st
  other arguments...:
>

How could you solve this problem?

A possibility is to define the function with a single argument which is a list. Here is a rewriting of your function in this way:

(define (even-odd-filter intlist)   
  (cond ((equal? '() intlist) '())
        ((equal? '() (cdr intlist)) intlist)
        ((equal? (modulo (car intlist) 2) (modulo (cadr intlist) 2))
         (cons (cadr intlist) (even-odd-filter (cons (car intlist) (cddr intlist)))))
        (else (even-odd-filter (cons (car intlist) (cddr intlist))))))

Upvotes: 0

Related Questions