The Little Schemer: What is a function or argument's structure?

Question

In Chapter 3 of The Little Schemer, the answer to the question of why we don't simplify the rember function right away is "because then a function's structure does not coincide with its argument's structure." I'm having trouble understanding what a function's structure is, what an argument's structure is, and what the difference is between them.

Here's the unsimplified version:

(define rember
  (lambda (a lat)
    (cond
      ((null? lat) (quote ()))
      (else (cond
        (( eq? (car lat) a) (cdr lat))
        (else (cons (car lat)
          (rember a
            ( cdr lat)))))))))

And here's the simplified:

(define rember
  (lambda (a lat)
    (cond
      ((null? lat) (quote ()))
      ((eq? (car lat) a) (cdr lat))
      (else (cons (car lat)
               (rember a (cdr lat)))))))

From what I can tell, the main difference is that the function has gone from two conds asking one question each to one cond asking two questions.

The function's arguments are the atom "a" and the list "lat."

This is the first time, outside of the densely written foreword, where the book references the word "structure." In my mind, the definition of the word "structure" so far is open to interpretation.

Someone has asked this exact question here before, but I have trouble following the answer. Why does a two-cond structure coincide or not coincide with the structure of a list? A list, in my mind, doesn't have any conditions at all!

Isn't a condition equivalent to a question in Scheme? Perhaps I'm misunderstanding what a condition is, which could be a reasonable root of my frustration. Anyways, any clarification on this would be very much appreciated! Thank you!

Answer 1

Here for “structure of function” the author probably means that the body of the function, that is the condition:

(cond
 ((null? lat) ...)
 (else ... (cond... (car lat) ... (cdr lat) ...)))

patterns exactly the “recursive” definition of a list, as either:

• an empty list, or
• a value with at least one element (the car), and a list (the cdr).

The new definition instead “folds” the two cond inside a single one, so that the “structure” of the function (the structure of the cond) does not reflect any more the “structure” of its list argument.

Answer 2

List is a type that could have been defined, with some pseudocode, as

(define-variant-record list
    ( () )               ; '() is a list
    ((hd . tl)           ; a cons pair (with car field named `hd` and cdr `tl`)
          (list tl)) )   ;  is a list, if `tl` itself is a list

Then, it could be handled with a hypothetical (cf. EOPL) patern-matching construct variant-case:

(define rember
  (lambda (a lat)        ; an atom and a list of atoms
    (variant-case (lat)  ; follow the `lat` --
      ( ()               ; an empty list case, or
          (quote ()))
      ( (hd . tl)        ; a non-empty list, with car field `hd` and cdr `tl`
          (cond 
             (( eq? hd a) tl)
             (else 
                (cons hd
                      (rember a tl))))))))

which, by way of using the variant-case belonging to the data-type definition of list, naturally and visibly follows its structure (i.e. the two cases of its definition).

The first formulation (with the nested conds) just emulates the non-existent variant-case with the explicit access to the concrete data-type implementation, with the cars and the cdrs as it does.

The inner cond does not belong to this, and just deals with the specifics of rember on its own. That's why mashing the two conds into one may be seen as mixing the non-related concerns into one mish-mash (generally speaking; although here both are extremely simple and clear).