Функция длины в The Seasoned Schemer

Я читал The Seasoned Schemer и наткнулся на это определение функции length.

(define length
  (let ((h (lambda (l) 0)))
    (set! h (L (lambda (arg) (h arg))))
    h))

Позже говорят:

Каково значение (L (лямбда (аргумент) (ч аргумент)))? это функция

(lambda (l)
  (cond ((null? l) 0)
     (else (add1 ((lambda (arg) (h arg)) (cdr l))))))

Я не думаю, что понимаю это полностью. Я думаю, мы должны определить L себя как упражнение. Я написал определение L в определении length, используя letrec. Вот что я написал:

(define length
  (let ((h (lambda (l) 0)))
    (letrec ((L
              (lambda (f)
                (letrec ((LR
                          (lambda (l)
                            (cond ((null? l) 0)
                                  (else
                                   (+ 1 (LR (cdr l))))))))
                  LR))))                  
    (set! h (L (lambda (arg) (h arg))))
    h)))

Таким образом, L принимает функцию в качестве аргумента и возвращает в качестве значения другую функцию, которая принимает список в качестве аргумента и выполняет рекурсию по списку. Я прав или безнадежно ошибаюсь в своей интерпретации? В любом случае определение работает

 (length (list 1 2 3 4))  => 4

scheme seasoned-schemer
person Rajesh Bhat    schedule 14.06.2012    source источник

Ответы (1)


arrow_upward
3
arrow_downward

В «Опытном интригане» length изначально определяется так:

(define length
  (let ((h (lambda (l) 0)))
    (set! h (lambda (l)
              (if (null? l)
                  0
                  (add1 (h (cdr l))))))
    h))

Далее в книге предыдущий результат обобщается, и length переопределяется в терминах Y! (комбинатор аппликативного порядка, императивный Y) следующим образом:

(define Y!
  (lambda (L)
    (let ((h (lambda (l) 0)))
      (set! h (L (lambda (arg) (h arg))))
      h)))

(define L
  (lambda (length)
    (lambda (l)
      (if (null? l)
          0
          (add1 (length (cdr l)))))))

(define length (Y! L))

Первое определение length, показанное в вопросе, является лишь промежуточным этапом - с процедурой L, точно такой же, как определено выше, вы не должны ее переопределять. Цель этой части главы — прийти ко второму определению, приведенному в моем ответе.

person Óscar López    schedule 14.06.2012