Little Schemer: напишите функцию, которая поддерживает только списки длиной ≤ 2
В книге "Маленький интриган" мы находим эту функцию, которая поддерживает только списки с длиной, меньшей или равной 1:
(((lambda (mk-length) ; A.
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l ) 0)
(else (add1 ((mk-length eternity ) (cdr l))))))))
'(1))
Я хочу изучать шаг за шагом, и хочу написать аналогичную функцию, которая поддерживает только списки длиной, меньшей или равной 2.
Пожалуйста, не отвечайте на этот вопрос, предлагая такой код:
(((lambda (mk-length) ; B.
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0 )
(else (add1((mk-length mk-length) (cdr l))))))))
'(a b c d))
потому что эта функция поддерживает любую длину.
И я уже знаю, как написать такую функцию:
(((lambda (mk-length) ; C.
(mk-length
(mk-length (mk-length eternity))))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
'(1 2)) ;;
чтобы достичь моей цели. Но этот код находится на расстоянии более одного шага от первого фрагмента.
Может быть, я не должен менять
(lambda (mk-length) ; D.
(mk-length mk-length)
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)))работает.
(NB: (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)))и таким образом работает для каждого списка, независимо от его длины.
И с помощью eta-конверсии это просто (mk-length mk-length),
Списки в Лиспе (Scheme, Common Lisp и т. Д.) Построены из cons-ячеек и специального (пустой список). Что когда у вас есть что-то, что является списком, это либо:
- Пустой список ()
- Сотовая ячейка (также называемая парой), где автомобиль пары - это первый элемент списка, а cdr пары - остальная часть списка.
Поскольку существует два типа списков, рекурсивные алгоритмы в списках обычно отвечают только на два вопроса:
- Каков результат для пустого списка?
- Каков результат для остальной части списка и как он превращается в результат для всего списка?
Для длины это означает:
- Длина пустого списка равна 0.
- Когда длина остальной части списка равна n, длина всего списка равна n + 1.
Тип решения, представленный в The Little Schemer, сначала разрабатывает решение, которое отвечает первому случаю, что означает, что оно работает для списков длиной ≤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