Рекурсивно обратная последовательность в Clojure

Question

Я хочу изменить последовательность в Clojure без использования функции reverse и сделать это рекурсивно.

Вот что я придумал:

(defn reverse-recursively [coll]
  (loop [r (rest coll)
         acc (conj () (first coll))]
    (if (= (count r) 0)
      acc
      (recur (rest r) (conj acc (first r))))))

Пример вывода:

user> (reverse-recursively '(1 2 3 4 5 6))
(6 5 4 3 2 1)
user> (reverse-recursively [1 2 3 4 5 6])
(6 5 4 3 2 1)
user> (reverse-recursively {:a 1 :b 2 :c 3})
([:c 3] [:b 2] [:a 1])

Вопросы:

1. Есть ли более краткий способ сделать это, то есть без цикла / повторения?
2. Есть ли способ сделать это безиспользуя параметр «аккумулятор» в цикле?

---

Ссылки:

Каков наилучший способ рекурсивного обращения строки в Java?

http://groups.google.com/group/clojure/browse_thread/thread/4e7a4bfb0d71a508?pli=1

Answer 1

• Тебе не нужно считать. Просто остановитесь, когда оставшаяся последовательность пуста.
• Не следует предварительно заполнять acc, так как исходный ввод может быть пустым (и это больше кода).
• Разрушение это круто.

(defn reverse-recursively [coll]
  (loop [[r & more :as all] (seq coll)
         acc '()]
    (if all
      (recur more (cons r acc))
      acc)))

Что касается loop / recur и acc, вам нужно каким-то образом обойти рабочий перевернутый список. Это либо loop, либо добавление еще одного параметра в функцию (что действительно делает loop в любом случае).

Или используйте функцию более высокого порядка:

user=> (reduce conj '() [1 2 3 4])
(4 3 2 1)

Answer 2

Ради исчерпывающего, есть еще один метод, использующий into.Поскольку для внутреннего использования conj он может использоваться следующим образом:

(defn reverse-list 
  "Reverse the element of alist."
  [lst]
  (into '() lst))

Answer 3

Да, на вопрос 1, это то, что я придумал для своего ответа на коан рекурсии (я не мог сказать вам, была ли это хорошая практика clojure или нет).

(defn recursive-reverse [coll]
    (if (empty? coll)
        []
        (conj (recursive-reverse (rest coll)) (first coll) )))

Answer 4

В текущей версии Clojure есть встроенная функция с именем rseq.Для тех, кто проходит мимо.

Answer 5

(defn recursive-reverse [coll]
  (if (empty? coll)
    ()
    (concat (vector (peek coll)) (recursive-reverse (pop coll )))
  )
)
and test:
user=> (recursive-reverse [1])       
(1)
user=> (recursive-reverse [1 2 3 4 5])
(5 4 3 2 1)

Answer 6

(defn reverse-seq [sss]
  (if (not (empty? sss))
    (conj (reverse-seq (rest sss)) (first sss))
  )
)

Answer 7

(defn my-rev [col]
  (loop [ col col
          result []]
        (if (empty? col)
            result
            (recur (rest col) (cons (first col) result)))))

Q1.

JVM не может оптимизировать рекурсию, рекурсивную функцию, которая бы напрямую и переполняла стек.Поэтому в Clojure, который использует цикл / recur.Таким образом, без использования функции, которая повторяет глубокую рекурсию, невозможно определить.(который также используется для рекурсии как батут функции.)

Q2.

рекурсивная функция по recur, должна быть хвостово-рекурсивной.Если обычная рекурсивная функция изменится на хвостовую рекурсивную функцию, то есть необходимость нести значение переменной, требуемой в качестве аккумулятора.