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!

Jeniferjeniffer

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.

Accrescent

Thank you! This makes sense to me. The pattern, then, in the simplified definition, would place all elements of a list within one bullet point, rather than two? – Jeniferjeniffer

@Jeniferjeniffer no, three - per the three cases in the "simplified" cond code. – Northernmost

In the simplified definition, the second case of the recursive definition of a list (a car which is an element, and a cdr which is a list), is “managed” by the second and the third branch of the condition, so that the original “two-way” structure of the cond is now a “three-way” structure, and the function is no more “parallel” to the structure of the list definition. A useful reference: L. Aiello, G. Attardi, and G. Prini. Towards a more declarative programming style. In Formal Description of Programming Concepts. North-Holland, 1978. Proc. IFIP TC-2 Conf., St. Andrews, Canada. – Accrescent

Ah, fantastic! This makes perfect sense to me. Thank you so much, Renzo and Will Ness! – Jeniferjeniffer

It's a pleasure for me! – Accrescent

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).

Northernmost

Thank you for your response! There is one point that I'd be extremely grateful for if you clarified. How does the simplified version not emulate the non-existent variant-case when it also hosts lines addressing a null list, a list with a car and cdr, and a recursion? – Jeniferjeniffer

the first version does emulate the variant-case, i.e. it does follow the data structure (here, list). ah, you meant the second. addressed in the edit. simply becasue data-type has two cases, not three. – Northernmost

Thank you for clarifying, Will Ness! Your response has been exactly what I needed to understand the problem. – Jeniferjeniffer