Кэширование значения «рекурсивного» вызова в Clojure с использованием recur

Question

Я выполняю Маленький интриган и Опытный интриган в Clojure как упражнение, чтобы выучить и Scheme, и Clojure - пытаясь записать его как идиоматический Clojure, насколько я могу , В гл. 14 ( Seasoned Schemer ) они определяют функцию leftmost, которая должна найти первый «атом» (имеется в виду сущность, которая не является списком, не определение Clojure атома ) в списке. Это моя реализация настоящей рекурсивной версии в Clojure:

(defn atom? [x]
  (not (coll? x)))

(defn leftmost [l]
  (cond
   (empty? l) []
   (atom? (first l)) (first l)
   :else (let [r (leftmost (first l))]
           (if (atom? r)
             r
             (leftmost (rest l))))))

Чтобы понять, что он делает, вот тесты для него:

(deftest test-leftmost
  (is (= :a (leftmost [:a :b [:c :d]])))
  (is (= :a (leftmost [[:a :b] [:c :d]])))
  (is (= :a (leftmost [[] [] [[:a]] :b [:c :d]])))
  (is (= [] (leftmost-recur [[] [['()]]])))
  (is (= [] (leftmost-recur []))))

Ключевой частью упражнения является «кэширование» вызова leftmost (first l) с помощью оператора let в предложении :else.

Я хочу написать это в Clojure, используя recur и получить оптимизацию оконечного вызова. Лучшее, что я могу сделать, это:

(defn leftmost-recur [l]
  (cond
   (empty? l) []
   (atom? (first l)) (first l)
   :else (let [r (leftmost-recur (first l))]
           (if (atom? r)
             r
             (recur (rest l))))))

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

Есть ли способ "кэшировать" вызов (let [r (leftmost-recur (first l))] без выполнения настоящей рекурсии?

Попытка использовать memoize

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

(defn leftmost-recur-memoize [l]
  (Thread/sleep 100)  ; added to check whether memoize is working    
  (let [memo-leftmost (memoize leftmost-recur-memoize)]
    (cond
     (empty? l) []
     (atom? (first l)) (first l)
     :else (let [r (memo-leftmost (first l))]
             (if (atom? r)
               r
               (memo-leftmost (rest l))
               )))))

... на основании тестовых чисел:

(println (time (= :a (leftmost-recur-memoize [:a :b [:c :d]]))))
(println (time (= :a (leftmost-recur-memoize [[] [] [[:a]] :b [:c :d]]))))
(println (time (= [] (leftmost-recur-memoize [[] [['()]]]))))
;; repeat same
(println (time (= :a (leftmost-recur-memoize [:a :b [:c :d]]))))
(println (time (= :a (leftmost-recur-memoize [[] [] [[:a]] :b [:c :d]]))))
(println (time (= [] (leftmost-recur-memoize [[] [['()]]]))))

"Elapsed time: 100.27427 msecs"
true
"Elapsed time: 701.740783 msecs"
true
"Elapsed time: 801.796439 msecs"
true
"Elapsed time: 100.148838 msecs"
true
"Elapsed time: 701.430802 msecs"
true
"Elapsed time: 801.767962 msecs"
true

Суть вопросов

Итак, наконец-то (извините за многословие), я прошу помощи по двум вопросам:

1. Есть ли способ кэшировать или запоминать оператор в оригинальном предложении else, не выполняя истинную / реальную рекурсию каждый раз?
2. Каков был бы самый идиоматический способ Clojure делать подобные вещи? (что может быть с функциями более высокого порядка или другим подходом)

Answer 1

1. Нет.Вложенный список списков - это дерево, и вы выполняете поиск в глубину.Каждый раз, когда вы выпадаете, вам нужно отслеживать все предыдущие списки, чтобы вы могли продолжить их проверять, когда возвращаетесь.Таким образом, такое поведение, требующее использования стека, на самом деле связано не с сохранением возвращенного значения, а с обходом дерева.

2. (first (flatten coll))