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)
