Little Schemer: напишите функцию, которая поддерживает только списки длины ≤ 2

TL;DR: (mk-length A) (внутри формы cond) вычисляет функцию length, которая работает для списков длиной 0, и будет использовать (A A) для вычисления length, которая будет использоваться для обработки хвоста (то есть результата (cdr ...)) списка аргументов.

Ваш первый фрагмент кода (;A.) работает только для списков длиной 0 и 1. Чтобы это работало и для 2, замените

                               (mk-length eternity)               ; length≤1

с участием

                               (mk-length   ; (2)                 ; length≤2
                                  (lambda (x) (mk-length eternity)))

работает.

(Примечание: (mk-length eternity) сама вычисляет length≤0, но общая функция становится length≤1; это — это то, на что ссылаются все дальнейшие length≤i комментарии.)

Глядя внимательно на

     (((lambda (mk-length)
          (mk-length mk-length))            
      (lambda (mk-length)                   ; (1)
          (lambda (l)                       
              (cond
                  ((null? l ) 0)
                  (else (add1 ((mk-length   ; (2)                 ; length≤2
                                  (lambda (x) (mk-length eternity)) )
                               (cdr l))))))))
     '(1 2))

мы видим, что результат (mk-length ...) в ;(2) используется для обработки (cdr l), в то время как argument в mk-length в ;(2) заменит mk-length в этом вызове при обработке (cddr l).

Если используется (mk-length eternity) (как в вашем первом коде), (cdr l) обрабатывается нормально, но ((eternity eternity) (cddr l)), естественно, терпит неудачу.

Если используется (mk-length (lambda (x) (mk-length eternity))), (cdr l) обрабатывается нормально, а затем ((lambda (x) (mk-length eternity)) (lambda (x) (mk-length eternity))) = (mk-length eternity) используется для обработки (cddr l), что также нормально (таким образом, длина 2 обрабатывается правильно), а затем ((eternity eternity) (cdddr l)), естественно, терпит неудачу (для длин 3 и выше).

Таким образом, чтобы обработать списки до трех элементов,

                              ((mk-length   ; (2)                 ; length≤3
                                  (lambda (x) (mk-length 
                                                (lambda (x) (mk-length eternity)))) )

может быть использован:

    (define (eternity x) (- 1))    ; to get an error instead of looping

    (((lambda (mk-length)
          (mk-length mk-length))
      (lambda (mk-length)
          (lambda (l)
              (cond
                  ((null? l ) 0)
                  (else (add1 ((mk-length   ; (2)                 ; length≤3
                                  (lambda (x) (mk-length
                                               (lambda (x) (mk-length eternity)))) )
                               (cdr l))))))))

      '(1 2 3))        ; => 3

    ; ...........
    ; '(1 2 3 4))      ; => **error**

Как вы правильно догадались, это — промежуточный шаг на пути к использованию

                     (mk-length (lambda (x) (mk-length x)))   ; (2)       ; length≤∞

что превращает обработку следующего элемента списка в

                     ((lambda (x) (mk-length x)) (lambda (x) (mk-length x)))
    =
                     (mk-length (lambda (x) (mk-length x)))

и, таким образом, работает для каждого списка, независимо от его длины.

А по эта-конверсии это всего (mk-length mk-length).

Списки в Лиспе (Scheme, Common Lisp и т.д.) строятся из cons-ячеек и специального (пустого списка). То есть всякий раз, когда у вас есть что-то, являющееся списком, это либо другое:

• Пустой список ()
• Cons-ячейка (также называемая парой), где car пары является первым элементом списка, а cdr пары является остальной частью списка.

Поскольку существует два типа списков, рекурсивные алгоритмы для списков обычно отвечают только на два вопроса:

• Каков результат для пустого списка?
• Каков результат для остальной части списка и как он превратился в результат для всего списка?

Для length это означает:

• Длина пустого списка равна 0.
• Когда длина остатка списка равна n, длина всего списка составляет n + 1.

Тип решения, представленный в Маленьком интригане, сначала разрабатывает решение, отвечающее первому случаю, что означает, что оно работает для списков длины 0. Как только у вас есть решение, которое обрабатывает оба случая (правильно ), у вас есть решение, которое работает для списков любой длины. Не существует реального инкрементного решения, которое расширило бы функцию для работы со списками длины 2.

Полагаю, вы могли сделать что-то вроде:

 (((lambda (mk-length)
      (mk-length mk-length))
  (lambda (mk-length)
      (lambda (l)
          (cond
              ((null? l ) 0)
              (else 1)))))

Это будет работать для списков длины 0 и списков длины 1 и будет некорректным для всех остальных списков, но для всех остальных списков будет возвращено 1. Если вы не измените структуру рекурсии, я думаю, что это действительно лучшее, что вы можете сделать. Если вы хотите изменить структуру рекурсии, вы можете сделать следующее:

 (((lambda (mk-length)
      (mk-length mk-length))
  (lambda (mk-length)
      (lambda (l)
          (cond
              ((null? l) 0)
              ((null? (cdr l)) 1)
              (else (add1 ((mk-length  eternity ) (cdr l))))))))

но вы на самом деле не должны использовать этот подход, потому что теперь вы обрабатываете списки в трех разных случаях вместо двух, что (почти) никогда не является тем, что вы хотите делать.

Перевод на Python

Можно ли переписать это мышление с помощью Python или другого языка обработки? До сих пор сложно представить автоматически созданное развлечение в рекурсии.

Тот же принцип работает в Python или любом другом языке, поддерживающем функции более высокого порядка. В Python более идиоматично локально определять функцию, а затем вызывать ее, а не напрямую вызывать лямбда-выражение, поэтому это может быть более читаемым для вас:

def length(l):
    def driver(recurse):
        "Returns the result of calling `recurse` with itself."
        return recurse(recurse);
    def zeroForEmptyListOrElseOnePlusRecurse(recurse):
        """Returns a function that returns 0 if its input is the
        empty list, or else returns one plus whatever calling 
        `recurse(recurse)` with the tail of the list returns."""
        def length(l):
            """Returns 0 if l is the empty list, and one plus
            the results of `(recurse(recurse))(l)` otherwise."""
            if l == []:
                return 0;
            else:
                _, *rest = l
                return 1+(recurse(recurse))(rest)
        return length
    return (driver(zeroForEmptyListOrElseOnePlusRecurse))(l)

print(length([1,2,3])) # 3
print(length([1,2]))   # 2
print(length([1]))     # 1
print(length([]))      # 0