Есть ли способ использовать итерацию в Common Lisp и избежать побочных эффектов одновременно?

Question

Я написал две версии функции LISP. Основное различие между ними состоит в том, что одно выполняется с помощью рекурсии, а другое - с помощью итерации.

Вот рекурсивная версия (без побочных эффектов!):

(defun simple-check (counter list)
  "This function takes two arguments: 
  the number 0 and a list of atoms. 
  It returns the number of times the 
  atom 'a' appears in that list."
  (if (null list)
      counter
      (if (equal (car list) 'a)
          (simple-check (+ counter 1) (cdr list))
          (simple-check counter (cdr list)))))

Вот итерационная версия (с побочными эффектами):

(defun a-check (counter list)
  "This function takes two arguments: 
  the number 0 and a list of atoms. 
  It returns the number of times the 
  atom 'a' appears in that list."
  (dolist (item list)
    (if (equal item 'a)
        (setf counter (+ counter 1))
        (setf counter (+ counter 0))))
  counter)

Насколько я знаю, они оба работают. Но я бы очень хотел избежать побочных эффектов в итерационной версии. Я бы хотел ответить на два вопроса:

1. Можно ли избежать побочных эффектов и сохранить итерацию?
2. Предполагая, что ответ на вопрос № 1 - да, каковы наилучшие способы сделать это?

Answer 1

Для полноты обратите внимание, что в Common Lisp есть встроенный COUNT:

(count 'a list)

Answer 2

Вы также можете перебирать с map, mapcar и друзьями.

https://lispcookbook.github.io/cl-cookbook/iteration.html

Я также предлагаю взглянуть на remove-if[-not] и другие reduce и apply:

(length (remove-if-not (lambda (x) (equal :a x)) '(:a :b :a)))  ;; 2

Answer 3

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

(loop :for x :in list
      :for counter := (if (eq x 'a) (1+ counter) counter)
      :finally (return counter))

Is counter установить на каждом шаге или отскок?Т.е., изменена ли существующая переменная (как в setf), или создана привязка новой переменной (как в рекурсии)?

Эта do версия очень похожа на рекурсивную версию:

(do ((list args (rest list))
     (counter 0 (+ counter (if (eq (first list) 'a) 1 0))))
    ((endp list) counter))

Тот же вопрос, что и выше.

Теперь «очевидная» loop версия:

(loop :for x :in list
      :count (eq x 'a))

Нет даже явной переменной длясчетчик.Есть ли побочные эффекты?

Внутренне, конечно, есть эффекты: создаются среды, устанавливаются привязки и, особенно, если есть оптимизация хвостового вызова, даже в рекурсивной версии, уничтожаемой / заменяемой на каждом шаге.

Я вижу как побочные эффекты только эффекты, которые влияют на вещи вне некоторой определенной области видимости.Конечно, все выглядит более элегантно, если вы также можете на уровне своего внутреннего определения избегать явного задания вещей и вместо этого использовать более декларативное выражение.

Answer 4

Передача счетчика в рекурсивную процедуру была средством включения определения хвостовой рекурсии.Это не нужно для итеративного определения.Как отмечали другие, есть несколько языковых конструкций, которые элегантно решают указанную проблему.

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

(defun simple-check (list)                                                                    
  "return the number of times the symbol `a` appears in `list`"                                 
  (let ((times 0))                                                                            
    (dolist (elem list times)                                                                 
      (when (equal elem 'a)                                                                   
        (incf times)))))