Clojure: может только возвращаться из положения хвоста

Я пытаюсь рекурсивно изменить список, но я получаю Can only recur from tail position при запуске. Что это значит точно и как мой код может быть улучшен, чтобы он работал?

(defn recursive-reverse [coll]
  (loop [coll coll]
    (if (< (count coll) 2) '(coll)
      (conj (first coll) (recur (rest coll)))
      )))

ИЗМЕНИТЬ

Выход для решения Oscar. Он работает для списков, но не для векторов?

user=> (= (recursive-reverse [1 2 3 4 5]) (recursive-reverse '(1 2 3 4 5)))
false
user=> (= '(1 2 3 4 5) [1 2 3 4 5])
true
user=> (recursive-reverse [1 2 3 4 5])
[1 2 3 4 5]
user=> (recursive-reverse '(1 2 3 4 5))
(5 4 3 2 1)

Ответы

Ответ 1

Ошибка Can only recur from tail position означает, что вы не вызываете recur в качестве последнего выражения в рекурсивной части функции - на самом деле в вашем коде conj есть последнее выражение.

Некоторые улучшения для работы вашего кода:

  • Спросите, является ли коллекция пустой в качестве базового аргумента, вместо сравнения, если ее длина меньше двух
  • conj получает коллекцию для своего первого параметра, а не элемента
  • Лучше использовать cons вместо conj (который добавляет новые элементы в разных местах в зависимости от конкретного типа коллекции, в соответствии с документация). Таким образом, возвращаемая коллекция будет отменена, если входная коллекция будет либо списком, либо вектором (хотя тип возвращаемой коллекции всегда будет clojure.lang.Cons, независимо от типа входной коллекции)
  • Помните, что '(coll) - это список с одним элементом (символ coll), а не фактическая коллекция
  • Для правильного обратного просмотра списка вам необходимо перебрать список входных данных и добавить каждый элемент в начало выходного списка; используйте параметр аккумулятора для этого
  • Для использования вызова хвостовой рекурсии recur в хвостовом положении функции; таким образом, каждый рекурсивный вызов занимает постоянное пространство, и стек не будет расти неограниченным.

Я считаю, что это то, к чему вы стремились:

(defn recursive-reverse [coll]
  (loop [coll coll
         acc  (empty coll)]
        (if (empty? coll)
            acc
            (recur (rest coll) (cons (first coll) acc)))))

Ответ 2

Вы можете вызывать recur только из положения хвоста в Clojure. Это часть дизайна языка, и это ограничение, связанное с JVM.

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

Вот пример из 4Clojure.com, где рекурсия используется без повторения.

(fn flt [coll]
  (let [l (first coll) r (next coll)]
    (concat 
      (if (sequential? l)
        (flt l)
        [l])
      (when (sequential? r)
        (flt r)))))

Ответ 3

Самый простой способ заставить ваш код работать - использовать имя функции вместо recur:

(defn recursive-reverse [coll]
  (loop [coll coll]
    (if (< (count coll) 2) '(coll)
      (conj (first coll) (recursive-reverse (rest coll)))
      )))

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

Вот еще один способ написать дружественную хвосту версию рекурсивного обратного:

(defn recursive-reverse [s]
  (letfn [
    (my-reverse [s c]
      (if (empty? s)
        c
        (recur (rest s) (conj c (first s)))))]
    (my-reverse s '())))

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

"Положение хвоста" означает, что recur - последнее, что делает функция перед ее возвратом. Это отличается от вашего решения "естественной рекурсии", в котором по-прежнему выполняется функция между вызовом и возвратом.