CODEWITHSUNDEEP
schemelispsicp
David542
David542

Reputation: 110173

Improving an iterative function in scheme

I often struggle writing iterative functions in scheme: it makes writing recursive procedures much simpler. Here is an example of trying to square items in a list using an iterative procedure:

(define square (lambda (x) (* x x)))
(define (square-list items)
  (define result nil) ; set result
  (define (iter items-remaining)
    (if (null? items-remaining)
        result
        (set! result (cons (car items-remaining) (iter (cdr items-remaining))))))
  (iter items))

(square-list '(1 2 3 4 5))
; (4 9 16 25)

My main question about this is:

Upvotes: 1

Views: 99

Answers (1)

ad absurdum
ad absurdum

Reputation: 21323

The posted code does not work; but even when fixed up so that it does work, this would not be an idiomatic Scheme solution.

To make the posted code work:

  • nil must be replaced with '(), since Scheme does not represent the empty list with nil
  • square must be called on the car of items-remaining
  • set! should modify result by adding squared numbers to it, not by trying to add the result of a recursive call. This won't work at all here because set! returns unspecified values; but even if it did work, this would not be tail-recursive (i.e., this would not be an iterative process)
  • The value of result must be returned, and it will have to be reversed first since result is really an accumulator

Here is a fixed-up version:

(define (square-list-0 items)
  (define result '()) ; set result
  (define (iter items-remaining)
    (cond ((null? items-remaining)
           result)
          (else
           (set! result (cons (square (car items-remaining))
                              result))
           (iter (cdr items-remaining)))))
  (iter items)
  (reverse result))

A better solution would not use mutation, and would not need (define result '()):

(define (square-list-1 xs)
  (define (iter xs acc)
    (if (null? xs)
        (reverse acc)
        (iter (cdr xs) (cons (square (car xs)) acc))))
  (iter xs '()))

Here an accumulator, acc, is added to the lambda list for the iter procedure. As results are calculated, they are consed onto acc, which means that at the end of this process the first number in acc is based on the last number in xs. So, the accumulator is reversed before it is returned.

Another way to do this, and probably a more idiomatic solution, is to use a named let:

(define (square-list-2 xs)
  (let iter ((xs xs)
             (acc '()))
    (if (null? xs)
        (reverse acc)
        (iter (cdr xs) (cons (square (car xs)) acc)))))

This is a bit more concise, and it lets you bind arguments to their parameters right at the beginning of the definition of the iter procedure.

All three of the above solutions define iterative processes, and all three give the same results:

> (square-list-0 '(1 2 3 4 5))
(1 4 9 16 25)
> (square-list-1 '(1 2 3 4 5))
(1 4 9 16 25)
> (square-list-2 '(1 2 3 4 5))
(1 4 9 16 25)

Of course, you could just use map:

> (map square '(1 2 3 4 5))
(1 4 9 16 25)

Upvotes: 3

Related Questions