Remove superfluous else from cond statement?

Question

I'm currently reading the 4th edition of "The Little Schemer". One early exercise is to create a function insertR which inserts an value to the right of a given value in a list. The book eventually arrives at the following definition:

(define insertR
  (lambda (new old lat)
    (cond
      ((null? lat) (quote ()))
      (else (cond
              ((eq? (car lat) old)
               (cons old
                     (cons new (cdr lat))))
              (else (cons (car lat)
                          (insertR new old
                                   (cdr lat)))))))))

My own definition looked like this:

(define insertR
  (lambda (new old lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) old) (cons old (cons new (cdr lat))))
      (else (cons (car lat) (insertR new old (cdr lat)))))))

Are they equivalent?

Answer 1

They are, yes, though I find yours easier to read. cond supports multiple clauses, and evaluates each until one of them evaluates to a true value. Thus, the following:

(else (cond
        ((eq? (car lat) old) (cons old (cons new (cdr lat))))
        (else (cons (car lat) (insertR new old (cdr lat)))))))))

Is equivalent to moving the first clause of the second cond to the first one:

(cond
  ((null? lat) (quote ()))
  ((eq? (car lat) old) (cons old (cons new (cdr lat))))
  (else (cons (car lat) (insertR new old (cdr lat)))))))

Perhaps the authors of the book thought it was more clear to separate the terminal null condition from the two others, but if that were the case, and if would suffice instead of cond.

Answer 2

Of course both definitions are equivalent, but your definition is easier to read. Bear in mind that you're only in the 3rd chapter of the book, and the authors like to go slowly. Later in the same chapter, on page 41 they'll teach you precisely the kind of simplification that you're doing - dealing with all mutually exclusive conditions in a single cond form, instead of nesting cond forms.

Answer 3

Yes, the two definitions have the same behavior.

The reason the book has two conds is because they are serving two different purposes. The outer cond distinguishes between the two cases of the list datatype (a list is either null or a cons whose second argument is a list). The outer cond is determined by the typed of data being consumed; all structurally-recursive functions on lists will have that outer cond. The inner cond is specific to the particular function being defined.

So, while it is more compact to combine them, by leaving them separate you make the structure of the function correspond more clearly to the structure of the recursive type. If you use that idiom consistently, it makes your structurally-recursive functions easier to read, debug, and maintain.

Answer 4

I'm going to say the same thing as Ryan: readability is second only to correctness. In fact, if you're a student, readability may be more important than correctness.

The advantage of the version that appears in the book is that it has a two-armed cond where one tests for emptiness. This is the totally normal and expected way to break down the problem. When I see this split, I can swiftly understand the role of the two blocks of code. In your code, I have to stop and spend time to make sure that the three cases are exhaustive and mutually exclusive, and then deduce which inputs fall into which bins.

Here's what I want you to picture: it's 11:52 PM, I'm tired, my eyes hurt, and I'm reading over forty-five solutions to the same problem, written by students. I'm looking for CLARITY, darn it. If you can write your solution in a way that makes it OBVIOUS that you did it right, I'm going to give you 100% and bless your name.