CODEWITHSUNDEEP
schemelispracketsicp
David542
David542

Reputation: 110163

Why is the empty list produced here in this iteration?

Let's take the following function to get a pair of numbers:

; (range 1 3) --> '(1 2 3)
(define (range a b)
  (if (> a b) nil
     (cons a (range (+ 1 a) b))))

; generate pair of two numbers with  1 <=  i < j <= N
(define (get-pairs n)
  (map (lambda (i)
         (map (lambda (j) (list i j))
              (range 1 (- i 1))))
       (range 1 n)))

(get-pairs 2)
; (() ((2 1)))

(get-pairs 3)
(() ((2 1)) ((3 1) (3 2)))

Why does the above produce '() as the first element of the output? Comparing this with python, I would expect it to just give the three pairs, something like:

>>> for i in range(1,3+1): # +1 because the range is n-1 in python
...     for j in range(1,i-1+1):
...         print (i,j)
...
(2, 1)
(3, 1)
(3, 2)

I suppose maybe it has to do with when i is 1?

(map (lambda (j) (list 1 j)) '())
; ()

Is that just an identity in Scheme that a map with an empty list is always an empty list?

Upvotes: 1

Views: 350

Answers (1)

ad absurdum
ad absurdum

Reputation: 21316

When i is 1, the inner map is over (range 1 0), which is () by your own definition. Since map takes a procedure and a list (or lists) of values, applies the procedure to each value in the list in turn, and returns a list containing the results, mapping any procedure over a list containing no values will return a list containing no values.

It might help to create a simple definition for map to see how this might work. Note that this definition is not fully featured; it only takes a single list argument:

(define (my-map proc xs)
  (if (null? xs)
      '()
      (cons (proc (car xs))
            (my-map proc (cdr xs)))))

Here, when the input list is empty, there are no values to map over, so an empty list is returned. Otherwise the procedure proc is applied to the first value in the input list, and the result is consed onto the result of mapping over the rest of the list.

A couple of observations:

First, the empty list is not represented by nil in either standard Scheme or vanilla Racket, and you should not be using it. In the early days of Scheme nil was allowed as a crutch for programmers coming from other lisps, but this has not been the case for a long time. I don't think that it was ever in any of the RnRS standards, but nil may have survived in some specific implementations until maybe R4RS (1991). SICP was from that era. Today you should use '() to represent empty list literals in Scheme so that your code can run on any Scheme implementation. Racket's #lang sicp allows code directly from the book to be run, but that should not keep you from using the common notation. Note that Common Lisp does use nil as a self-evaluating symbol to represent both the empty list, and boolean false. Seeing this in Scheme just doesn't look right today.

Second, you will probably be led astray more often than to wisdom by thinking in terms of Python when trying to understand Scheme code. In this particular case, map is an iteration construct, but it is not the same thing as a for loop. A for loop is usually used for side-effects, but map is used to transform a list. Scheme has a for-each form which is meant to be used for its side-effects, and in that sense is more like a for loop. The Python version that is posted above is not at all like the Scheme version, though. Instead of returning the results in a list, the results are printed. In the Scheme code, when i is 1, the inner mapping is over (range 1 0) --> (). But, in the Python code, when i is 1, the inner loop is over range(1, 1), so the body of this for loop is not executed and nothing is printed.

Better to think carefully about the Scheme code you want to understand, falling back on basic definitions, than to cobble together a model based on Python that has possibly unconsidered corner cases.

Upvotes: 1

Related Questions