Caching the value of a “recursive” call in Clojure using recur

Question

I am doing the The Little Schemer and The Seasoned Schemer exercises in Clojure as an exercise to learn both Scheme and Clojure - trying to write it in as idiomatic Clojure as I can. In Ch. 14 (Seasoned Schemer) they define the function leftmost, which should find the first "atom" (meaning an entity that is not a list, not the Clojure definition of an atom) in a list. This is my implementation of the true recursive version in 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))))))

To make it clear what it does, here are the tests for it:

(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 []))))

The key part of the exercise is to "cache" the call of leftmost (first l) by using a let statement in the :else clause.

I want to write this in Clojure using recur and get tail call optimization. The best I can do so far is this:

(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))))))

In the :else clause I've still got a true recursion, not recur, because recur must of course appear in a tail-call position. This function passes the test, but is subject to the problems of true recursion, including stack overflows.

Is there a way to "cache" the (let [r (leftmost-recur (first l))] call without doing true recursion?

Attempt to use memoize

I tried to think about using memoize, but I'm not sure how to memoize a self-recursive function. Here was my attempt, but I don't think it is doing what I hoped:

(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))
               )))))

... based on the test numbers:

(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

The bottom line questions

So, at long last (sorry for the verbosity), I am asking for help on two questions:

Is there a way to cache or memoize the statement in the original else clause without doing true/actual recursion every time?
What would be the most idiomatic Clojure way of doing this type of thing? (which might be with higher order functions or some other approach)

Alex Taggart Alex Taggart · Accepted Answer · 2011-12-31T22:48:14

No. A nested list of lists is a tree, and you're performing a depth-first search. Every time you drop down, you need to keep track of all the previous lists so that you can continue checking them when you come back up. So that stack-consuming behaviour is not really due to storing the returned value, but rather due to traversing a tree.
(first (flatten coll))

Caching the value of a “recursive” call in Clojure using recur

Attempt to use memoize

The bottom line questions

1 Answers