Паттерны для создания рекурсивных функций.

Читая An Introduction to Programming in Emacs Lisp, наткнулся на описание простых рекурсивных паттернов и решил сделать их описание.

Паттерн every.

В данном паттерне действие выполняется над каждым элементом списка. Алгоритм паттерна следующий:

• 
  Если список пустой, то возвращаем nil.
  
• 
  В противном случае работаем над началом списка(операция car). После чего делаем рекурсивный вызов с использованием cdr или комбинируем результат функции с помощью cons.
  

Пример использования:

(defun square-each (numbers-list)
"Square each of a NUMBERS LIST, recursively."
    (if (not numbers-list)
        nil
        (cons (* (car numbers-list) (car numbers-list)) 
            (square-each (cdr numbers-list)))))

(square-each ’(1 2 3))
⇒ (1 4 9)

В данном примере каждый элемент списка возводится в квадрат.
Еще один пример:

(defun print-elements-recursively (list)
"Print each element of LIST on a line of its own. Uses recursion."
    (when list
        (print (car list))
        (print-elements-recursively (cdr list))))

В приведенном примере функция рекурсивно выводит каждый элемент.

Паттерн accumulate.

В этом паттерне действие производится над каждым элементом списка и результат
этого действия аккамулируется с результатом последующих элементов. Алгоритм имеет вид:

• 
  Если список пуст, то возвращается нуль или любая другая константа.
  
• 
  Иначе берется первый элемент списка и объеденяется с последующими элементами
  рекурсивного вызова с помощью функции + или подобными ей комбинирующими функциями.
  

Пример:

(defun add-elements (numbers-list)
"Add the elements of NUMBERS-LIST together."
      (if (not numbers-list)
         0
         (+ (car numbers-list) (add-elements (cdr numbers-list)))))

(add-elements ’(1 2 3 4))
⇒ 10

Таким образом функция выводит сумму всех элементов списка.

Паттерн keep.

В данном паттерне каждый элемент списка проходит проверку. Если он удовлетворяет условию, то результат действия сохраняется.
Алгоримт имеет вид:

• Если список пуст, то возвращаем nil.
• Если начальный элемент списка проходит проверку, то комбинируем его с помощью cons и делаем рекурсивный вызов с хвостом списка(cdr).
• В противном случае если первый элемент не удовлетворяет условию, то действие над данным элементом пропускается и с помощью рекурсивного вызова переходим на следующий элемент.

Пример:

(defun keep-three-letter-words (word-list)
"Keep three letter words in WORD-LIST."
     (cond ((not word-list) nil)
           ((eq 3 (length (symbol-name (car word-list))))
               (cons (car word-list) (keep-three-letter-words (cdr word-list))))
           (t (keep-three-letter-words (cdr word-list)))))

(keep-three-letter-words ’(one two three four five six))
⇒ (one two six)

В выше приведенном примере выделяется список символов, длина которого равна 3.