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

18

Я пытаюсь рекурсивно отменить список, но я получаю 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)
    
задан Chris 02.06.2012 в 18:47
источник
  • он работает по-разному для списков и векторов, потому что conj работает по-разному для обоих. Это самый дешевый элемент «добавить» в начало списка и до конца вектора. conj смотрит на тип коллекции и добавляет ее самым дешевым способом. Честно говоря, это мне никогда не нравилось, но я уверен, что Rich Hickey и другие разработчики Clojure очень тщательно подумали об этом и решили, что профи перевешивают любые минусы. –  Gert 02.06.2012 в 22:47
  • Увлекательный. Я думаю, что производительность была их первостепенной задачей для основных операций, но да, это кажется странным. –  Chris 02.06.2012 в 22:50
  • Пятно на, @Gert. Я обновил свой ответ, я бы скорее вернул правильный ответ другого типа, чем неправильный ответ, если вход представляет собой вектор –  Óscar López 02.06.2012 в 23:01

3 ответа

20

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

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

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

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

(defn recursive-reverse [coll]
  (loop [coll coll
         acc  (empty coll)]
        (if (empty? coll)
            acc
            (recur (rest coll) (cons (first coll) acc)))))
    
ответ дан Óscar López 02.06.2012 в 20:22
  • Спасибо за замечательный ответ. Новая тайна: почему это работает с векторами, но не списками? Я отправил свой ответ на вопрос leon в вопросе. –  Chris 02.06.2012 в 22:36
  • Это происходит из-за того, как работает conj: «« Добавление »может происходить в разных« местах »в зависимости от конкретного типа». Если мы изменим conj для cons (как я только что сделал в своем ответе), возвращаемая последовательность всегда будет отменена, но тип коллекции будет clojure.lang.Cons. Взгляните на это сообщение для объяснения –  Óscar López 02.06.2012 в 22:50
6

Вы можете только вызывать 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)))))
    
ответ дан octopusgrabbus 02.06.2012 в 19:18
2

Самый простой способ заставить ваш код работать - использовать имя функции вместо 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 - это последнее, что делает функция перед ее возвратом. Это отличается от вашего решения «естественной рекурсии», в котором все еще выполняется работа между функцией между вызовом и возвратом.

    
ответ дан Nathan Hughes 02.06.2012 в 21:40
  • почему вы использовали letfn вместо цикла с двумя аргументами? Использование цикла более идиоматично. –  Gert 02.06.2012 в 22:17
  • @Gert: это просто еще один способ сделать это, я думал, что если OP не был знаком с циклом, тогда letfn может иметь больше смысла. есть ли источник идиоматического суждения? на самом деле я понял, что писать это с помощью аккумулятора не было идиоматическим (основано на чем-то в Радости Клоюре) в любом случае независимо. –  Nathan Hughes 02.06.2012 в 22:25
  • , это хороший момент. Но цикл существует именно для этого случая (создавая точку рекурсии, которая не является вызовом функции), она также более сжата, широко используется и проиллюстрирована / документирована на clojure.org/special_forms –  Gert 02.06.2012 в 22:43