Вместо того, чтобы дать вам ответ, который просто поможет вам сдать домашнее задание, не задумываясь, я постараюсь дать ответ, который поможет вам подумать о проблеме и других подобных проблемах, например хакер-лисп.
Для этого подумайте об алгоритме решения этой проблемы:
Если мы знаем, сколько вхождений того, что мы ищем, в списке на данный момент, то:
- если список пуст, то ответом является число, которое мы видели до сих пор;
- в противном случае список не пуст, и -
- , если первый элементсписок такой же, как и то, что мы рассчитываем, тогда ответ - это количество вхождений в остальной части списка, если предположить, что мы увидели на один больше, чем мы видели ранее;
- , если первый элементсписок не совпадает с тем, что мы рассчитываем, тогда ответ - это число случаев в остальной части списка, при условии, что мы видели то же число, которое мы уже видели.
И все. Ну, мы можем очень легко превратить это в код: очевидно, это спецификация рекурсивной функции с базовым регистром для рекурсии, когда список пуст. Но чтобы сделать вещи более интересными, мы сильно ограничим части языка, который мы можем использовать. В частности, в тексте определения:
- функция не может знать свое собственное имя;
- единственная конструкция связывания переменных, которую мы можем использовать, это
lambda.
Первый трюк заключается в том, как использовать lambda для привязки переменных. Ну, это легко, потому что lambda делает связывание переменных:
((lambda (x) ... here x is bound to 1 ...) 1)
Второй трюк состоит в том, что если функции не разрешено знать свое имя, то способ, которым она должна вызыватьсам по себе передается сам в качестве одного из аргументов. Итак, внутренности функции выглядят так:
(lambda (c elt tail count-so-far)
;; Here:
;; - c is the function we must call to count the rest of the list
;; (it's this function!);
;; - elt is the thing we are looking for;
;; - tail is the tail of the list we are searching;
;; - count-so-far is the count of elements found so far
;;
(if (null tail)
;; we're done: count-so-far is the count
count-so-far
;; There is more to do. eql is the appropriate 'is this the same
;; as that' predicate in this case.
(if (eql elt (first tail))
;; we've found one, so we need to recurse with the count being one more
(funcall c c elt (rest tail) (+ count-so-far 1))
;; we didn't find one
(funcall c c elt (rest tail) count-so-far))))
Раздражающая вещь в этом коде состоит в том, что для вызова функции мы должны сделать это (funcall c c ...): причина этого в том, чточто CL - это то, что называется Lisp-2, поэтому в такой форме, как (f x), f ищется в другом пространстве имен (другом пространстве привязок), чем x: funcall - это то, что мы должны использоватьсказать «вызов функции, которую я связал с этой переменной». В любом случае мы вызываем все, что связано с c, передавая его в качестве первого аргумента, чтобы он, в свою очередь, мог вызывать себя.
Теперь мы должны инициировать процесс, связывая эту вещь спеременная, а затем вызвать его. Мы можем сделать это, используя lambda, как указано выше.
((lambda (f)
;; kick off the recursion: at the start the count of elements seen
;; so far is 0.
(funcall f f the-element list 0))
(lambda (c elt tail count-so-far)
;; Here:
;; - c is the function we must call to count the rest of the list
;; (it's this function!);
;; - elt is the thing we are looking for;
;; - tail is the tail of the list we are searching;
;; - count-so-far is the count of elements found so far
;;
(if (null tail)
;; we're done: count-so-far is the count
count-so-far
;; There is more to do. eql is the appropriate 'is this the same
;; as that' predicate in this case.
(if (eql elt (first tail))
;; we've found one, so we need to recurse with the count being one more
(funcall c c elt (rest tail) (+ count-so-far 1))
;; we didn't find one
(funcall c c elt (rest tail) count-so-far)))))
И, наконец, мы можем обернуть это в обычное определение функции, которое мы позволим себе использовать на верхнем уровне:
(defun count-of (the-element list)
;; Count the-element in list
((lambda (f)
;; kick off the recursion: at the start the count of elements
;; seen so far is 0.
(funcall f f the-element list 0))
(lambda (c elt tail count-so-far)
;; Here:
;; - c is the function we must call to count the rest of the list
;; (it's this function!);
;; - elt is the thing we are looking for;
;; - tail is the tail of the list we are searching;
;; - count-so-far is the count of elements found so far
;;
(if (null tail)
;; we're done: count-so-far is the count
count-so-far
;; There is more to do. eql is the appropriate 'is this the
;; same as that' predicate in this case.
(if (eql elt (first tail))
;; we've found one, so we need to recurse with the count
;; being one more
(funcall c c elt (rest tail) (+ count-so-far 1))
;; we didn't find one
(funcall c c elt (rest tail) count-so-far))))))
Вы можете сделать несколько упрощений: рекурсивная функция может просто полагаться на привязки, сделанные во внешней функции, и мы можем слегка вывернуть рекурсивный вызов наизнанку:
(defun count-of (the-element list)
;; Count the-element in list
((lambda (f)
;; kick off the recursion: at the start the count of elements
;; seen so far is 0.
(funcall f f list 0))
(lambda (c tail count-so-far)
;; Here:
;; - c is the function we must call to count the rest of the list
;; (it's this function)l
;; - tail is the tail of the list we are searching;
;; - count-so-far is the count of elements found so far
;;
(if (null tail)
;; we're done: count-so-far is the count
count-so-far
;; There is more to do. eql is the appropriate 'is this the
;; same as that' predicate in this case.
(funcall c c (rest tail)
(+ count-so-far (if (eql the-element (first tail)) 1 0)))))))
Это, однако, не является улучшением: оно немного короче.
И мы можем видеть эту работу:
> (count-of 'a '(1 2 3 4 a (a a a) a 5))
2
> (count-of 'a '(1 2 3 4 (a a a) a 5))
1
> (count-of 'a '(1 2 3 4 (a a a) 5))
0
Для дополнительной информации здесь приведена версия последней версии. выше на языке, который является Lisp-1, поэтому нам не нужно funcall. Это Ракетка :
(define count-of
(λ (the-element lst)
((λ (f)
(f f lst 0))
(λ (c tail count-so-far)
(if (null? tail)
count-so-far
(c c (rest tail)
(+ count-so-far (if (eqv? the-element (first tail)) 1 0))))))))