Лисп/Рекурсия
Рассмотрим простейший пример рекурсивного копирования списка:
(defun my-copy-list (A)
"Выдаёт копию данного линейного списка. (Аналог встроенной copy-list.)"
(if (null A)
A
(cons (car A) (my-copy-list (cdr A)))))
;; >> (my-copy-list '(a b (c d))) => (A B (C D))
У рекурсивной функции две или более вычислительных «ветви», причём одна обязательно ведёт к завершению вычислений. В другой — рекурсивной — ветви (каковая в данном случае единственна) функция строит список из головного элемента (car A)
и списка, который получается в результате вызова той же функции my-copy-list
с аргументом (cdr A)
— обезглавленным исходным списком. Так повторяется до тех пор, пока не будет истинным (null A)
, то есть аргумент вызываемой функции не станет пустым списком; в этом случае вычисления завершаются.
Наша my-copy-list
копирует только верхний уровень списка (дерева), ведь очередной головной элемент (car A)
вполне может сам быть списком, — но функция копирует его целиком, не глядя. Это не позволяет, например, использовать функции с такой структурой для поиска отдельных атомов, потому что она найдет только (C D)
, но не C и D по отдельности. Определим функцию my-copy-tree
, копирующую список, — потенциальное дерево — рекурсивно:
(defun my-copy-tree (D)
(cond ((null D) nil)
((atom D) D)
(t (cons (my-copy-tree (car D))
(my-copy-tree (cdr D))))))
Здесь рекурсивный вызов проходится не только по cdr
, но и по car
текущего списка.
По сути, вас никто не обязывает выстраивать элементы исходного списка в том же порядке: заменив
(cons (new-copy-tree (car tree)) (new-copy-tree (cdr tree)))
на (cons (new-copy-tree (cdr tree)) (new-copy-tree (car tree)))
, наша функция будет строить список в обратном порядке. Так можно было бы определить аналог встроенной reverse
.
Скелеты приведенных выше функций - довольно распространенные лисповские идиомы.
Например, вы можете определить функцию my-append
— аналог append
, объединяющую списки:
(defun new-append (list1 list2)
(if (null list1)
list2
(cons (car list1)
(new-append (cdr list1) list2))))
Ее конструкция очень напоминает new-copy-list. Таких функций можно придумать довольно много. Если вы захотите использовать их в своей программе, то можете написать функцию
>> (defun template (arg1 &optional arg2 (func #'cons))
(if (null arg1)
arg2
(funcall func (car arg1) ;funcall - применение функции func к ее аргументам
(template (cdr arg1) arg2 func)))) => TEMPLATE
решетка с кавычкой говорят интерпретатору, что следующий за ним аргумент - функционал (функция с заранее неизвестными аргументами). Интерпретатор не вычисляет значение функционала, "посаженного за решетку", а применяет к нему нужные аргументы (funcall) по нашей просьбе.
вызов template с нужными аргументами позволяет превратить ее в new-copy-list, append или что-то еще (например, такой же вид будет иметь функция для замены, вставки, удаления атомов в списке)
>> (template '(a b (c d))) ; вызов с одним аргументом - копия списка
<< (A B (C D))
>> (template '(a b) '(c d)) ; два аргумента - объединение списков
<< (A B C D)
;; etc
Это напоминает шаблоны в C++ (ой, что я сказал?! ведь концепция шаблонов вместе с ООП пришла в C++ именно из лиспа :-) Такой подход позволяет значительно улучшить программу, сделать ее модульной и расширяемой, это один из примеров восходящего программирования