Basic reverse function

Question

I am just starting out in my Clojure journey and I wonder if anybody can point out my beginners mistakes in my function below that simply reverses a list. I know that there is already a reverse function so this is purely for learning.

(defn rev
  ([l]
   (if (= (count l) 1) l (rev '() l)))
  ([l orig]
   (if (= (count orig) 0)
     l
     (rev (conj l (first orig)) (rest orig)))))

In my defence, it does work, but what I am finding myself doing a lot in Clojure is overloading the arguments list to take into account when I need a working list like in this example where I conj new items onto.

Answer 1

Sometimes using arity overloading like you've done is the best way to write a function.

I tried to rewrite your function using destructuring, like this:

(defn rev [[x & more]]
  (if more
    ...

however, it doesn't really work because you need some way of storing your "result sequence" in progress, which in your function is l. Because we're trying to write a reverse function, it's hard to do what we want without having some way of "building up" the sequence as we go and storing it in an intermediate value.

Taking a look at how reverse is actually implemented in Clojure, we can see that a more concise way to express this idea of iterating over a sequence and building up a result sequence is by using reduce with a starting value of '():

(defn reverse [coll]
  (reduce conj '() coll))

The magic behind this is that we're starting with a seq, '(). When you conj something onto a seq, it adds it to the beginning, not the end. So what this does is it starts with an empty seq, then goes through the input list items one by one and adds them to the beginning of the result list, so that you end up with a list that's reversed.

EDIT: Leonid has a more thorough answer here.

Answer 2

• The 2 argument version of your function ought not to be exposed. Define it with a let or letfn form instead.
• You say you are reversing a list. Wherever you call for a list, a lazy sequence can turn up. Then count runs right to the end of the sequence every time. SLOW, for sequences of any length. So use empty? instead.
• You deal with case 1 of length separately. There is no need to.
• (More advanced) You are using explicit recursion: consuming one stack frame for every element in the original sequence. This sets a fairly low limit on the length of the list you can deal with: probably
  around the 10K mark (YMMV). Luckily, the recursive call to rev is the last thing that happens: you can replace it with recur.
• And - trivially - you don't need to quote ().

Those who don't want to see the outcome should look away now.

(defn rev [l] 
  (letfn [(rev2 [l orig]
          (if (empty? orig)
            l
            (recur (conj l (first orig)) (rest orig))))]
    (rev2 () l))) 

This is pretty well what you get using the standard reverse: though it's much more concisely expressed using reduce.