loop/recur and tail postion

[Kevin Sookocheff]

Hi, I'm going through some Scheme code to learn Clojure.  I defined a function

rember

as
 

(defn rember [atom l]
        (loop [a atom lat l]
           (cond
             (empty? lat) `()
             (= (first lat) a) (rest lat)
             :else (cons (first lat) (recur a (rest lat))))))

To which the REPL responds:

Can only recur from tail position
  [Thrown class java.lang.UnsupportedOperationException]

Is the call to recur not in tail position here?

Thank you,

Kevin

[Jonas]

Is the call to recur not in tail position here?

No, because of (cons (first lat) (recur a (rest lat))). You cons (first lat) after you call (recur ...). That is why (recur ...) is not in tail position. 

[Meikel Brandmeyer]

Hi,

no, it's not. The cons is in the tail position. Here a working version.

(defn rember
  [a l]
  (loop [ret []
         lat (seq l)]
    (cond
      (not lat)         ret
      (= (first lat) a) (recur ret (next lat))
      :else             (recur (conj ret (first lat)) (next lat)))))

Note, how recur is now in the tail position and how an accumulator is used to collect the results.

Hope that helps.

Sincerely
Meikel

BTW: you can also use direct recursion in your original function instead of recur by simply calling the function (rember) itself again.

[Ken Wesson]

Nope. The return from recur has to be, directly, the return from the
enclosing loop form for it to be a tail position. Here you're consing
something onto it in between. Generally that means you need to add a
result accumulator to the loop, something like:

(defn rember [atom l]
(loop [a atom lat l res []]
(cond
(empty? lat) res

(= (first lat) a) (rest lat)

:else (recur a (rest lat) (conj res (first lat))))))

though I can think of further improvements, like hoisting a out of the
loop (it doesn't change) and using seq/next like so:

(defn rember [atom l]
(loop [lat (seq l) res []]
(if lat
(let [f (first lat)]
(if (= f atom)
(rest lat)
(recur (next lat) (conj res f))))
res)))

--
Protege: What is this seething mass of parentheses?!
Master: Your father's Lisp REPL. This is the language of a true
hacker. Not as clumsy or random as C++; a language for a more
civilized age.

[Kevin Sookocheff]

Thanks everyone.  Makes perfect sense.