2
\$\begingroup\$

I'm writing a function that returns all (nested) sequences reversed:

(defn my-reverse-v1 [input]
  (let [head (first input)
        tail (rest input)]
    (if head
      (conj (my-reverse-v1 (vec tail))
            (if (sequential? head)
              (my-reverse-v1 (vec head))
              head))
      [])))

(defn my-reverse-v2 [initial input]
  (let [head (first input)
        tail (rest input)]
    (if head
      (recur (cons (if (sequential? head) (my-reverse-v2 [] head) head) initial) tail)
      (vec initial))))

(defn test-my-reverse []
  (let [input [[1 2] 3 [4 [5 6]] 7 [8 [9 [10 11] 12]]]
        expected [[[12 [11 10] 9] 8] 7 [[6 5] 4] 3 [2 1]]]
    (println "my-reverse-v1:" (= expected (my-reverse-v1 input)))
    (println "my-reverse-v2:" (= expected (my-reverse-v2 [] input)))))

my-reverse-v2 is the tail-recursive version, whereas my-reverse-v1 isn't. These two functions work as expected, but I think there will be lots more succinct or Clojure-ish implementations for the requirements.

\$\endgroup\$
1
\$\begingroup\$

For an extremely short version of the (not tail-) recursive algorithm, I recommend using walk. You can write the code with walk like this:

(defn my-reverse-v3 [input]
  (walk #(if (sequential? %) (my-reverse-v3 %) %) reverse input))

For a properly tail-recursive version, my cleanest results use clojure.zip:

(defn my-reverse-v4 [input]
  (loop [z-input
         (zipper sequential? seq (fn [_ c] c) input)]
    (if (end? z-input)
      (root z-input)
      (recur (next (edit z-input #(if (sequential? %) (reverse %) %)))))))

For this solution, I followed a structure which I found at Exploration through Example.

(Incidentally, your my-reverse-v2 is not tail-recursive. The function calls itself within a call to cons. One of the nice things about Clojure's recur is that it will throw a compile error when it's not used in a tail-recursive position; you'd surely see that in action here.)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.