Маленький интриган: что такое структура функции или аргумента?

Question

В главе 3 "Маленького планировщика" ответ на вопрос о том, почему мы не упрощаем сразу функцию "Рембер", заключается в том, "что тогда структура функции не совпадает со структурой ее аргумента". У меня возникают проблемы с пониманием структуры функции, структуры аргумента и разницы между ними.

Вот не упрощенная версия:

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

И вот упрощенное:

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

Из того, что я могу сказать, основное отличие состоит в том, что функция перешла от двух cond, задающих один вопрос каждый к одному cond, задающему два вопроса.

Аргументами функции являются атом "a" и список "lat".

Впервые за пределами плотно написанного предисловия в книге упоминается слово "структура". На мой взгляд, определение слова "структура" до сих пор открыто для толкования.

Кто-то задавал этот точный вопрос здесь раньше, но у меня возникли проблемы с ответом. Почему двухкондовая структура совпадает или не совпадает со структурой списка? Список, на мой взгляд, не имеет никаких условий вообще!

Разве условие не эквивалентно вопросу в схеме? Возможно, я неправильно понимаю, что такое состояние, которое может быть разумным корнем моего разочарования. В любом случае, любые разъяснения по этому поводу будут очень благодарны! Спасибо!

Answer 1

Здесь под "структурой функции" автор, вероятно, подразумевает тело функции, то есть условие:

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

Шаблоны точно "рекурсивное" определение списка, как либо:

• пустой список, или
• значение, по крайней мере, с одним элементом (автомобилем) и списком (cdr).

Новое определение вместо этого "складывает" два cond внутри одного, так что "структура" функции (структура cond) больше не отражает "структуру" своего аргумента списка.

Answer 2

Список - это тип, который может быть определен с некоторым псевдокодом, как

(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

Затем он может быть обработан с помощью гипотетической (см. EOPL) патерно-согласующей конструкции 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))))))))

который, используя variant-case принадлежность к определению типа данных listестественно и наглядно следует его структуре (то есть двум случаям ее определения).

Первая формулировка (с вложенными conds) просто эмулирует несуществующее variant-case с явным доступом к конкретной реализации типа данных, с carс и cdrкак оно есть.

Внутренний cond к этому не относится, а просто занимается спецификой rember сам по себе. Вот почему пюре двух conds в один может рассматриваться как смешение несвязанных проблем в одну мешанину (вообще говоря, хотя здесь оба чрезвычайно просты и понятны).