Clojure: rest vs. next

I'm having a hard time understanding the difference between rest and next in Clojure. The official site's page on laziness indicates that the preference should probably be to use rest, but it doesn't really explain clearly the difference between the two. Can anybody provide some insight?

As the page you linked described, next is stricter than (the new behaviour of) rest because it needs to evaluate the structure of the lazy cons to know whether to return nil or a seq.

rest on the other hand always returns a seq, so nothing needs to be evaluated until you actually use the result of rest. In other words, rest is more lazy than next.

It's easy if you have this:

(next '(1))
=> nil

So next looks at the next thing and if the line is empty it returns nil instead of an empty seq. This means that it needs to look ahead (to the first item it would return) which makes it not fully lazy (maybe you don't need the next value, but next wastes the compute time to look ahead).

(rest '(1))
=> ()

rest doesn't look ahead and just returns the rest of the seq.

Maybe you think, Why even bother using two different things here? The reason is that you normally want to know if there is nothing left in the seq and just return nil, but in some cases where performance is very important and evaluating one more item could mean tremendous effort you can use rest.

next is like (seq (rest ...)).

rest will return the remaining piece of a sequence. If that piece of the sequence has not yet been realized, rest doesn't force it. It won't even tell you if there are more elements left in the sequence.

next does the same thing but then forces at least one element of the sequence to be realized. So if next returns nil, you know there aren't any more elements left in the sequence.

I now prefer to use next with recursion, as the escape-evaluation is simpler/cleaner:

(loop [lst a-list]
    (when lst
        (recur (next lst))

vs

(loop [lst a-list]
    (when-not (empty? lst)   ;; or (when (seq? lst)
        (recur (rest lst))

A case for using rest, though, would be if you use a collection as a queue or stack. In that case you want your function to return an empty collection when popping or dequeueing the last item.

Here is a little table useful when writing code that traverses a sequence using "mundane" recursion (using the stack) or using recur (using tail-recursive optimization, thus actually looping).

Note the differences in behaviour of rest and next. Combined with seq this leads to the following idiom, where end-of-list is tested via seq and rest-of-list is obtained via rest (adapted from "The Joy of Clojure"):

; "when (seq s)":
; case s nonempty -> truthy -> go
; case s empty    -> nil -> falsy -> skip
; case s nil      -> nil -> falsy -> skip

(defn print-seq [s]
  (when (seq s)          
     (assert (and (not (nil? s)) (empty? s)))
     (prn (first s))     ; would give nil on empty seq
     (recur (rest s))))  ; would give an empty sequence on empty seq

Why is next more eager than rest?

If (next coll) is evaluated, the result can be nil. This must be known immediately (i.e. nil must actually be returned) because the caller may branch on based on the truthyness of nil.

If (rest coll) is evaluated, the result cannot be nil. Unless the caller then tests the result for empty-ness using a function call, generation of a "next element" in a lazy-seq can be delayed to the time it is actually needed.

Example

A completely lazy collection, all the computations are "on hold until needed"

(def x
   (lazy-seq
      (println "first lazy-seq evaluated")
      (cons 1
         (lazy-seq
            (println "second lazy-seq evaluated")
            (cons 2
               (lazy-seq
                  (println "third lazy-seq evaluated")))))))           
 
;=> #'user/x

The computation of "x" is now suspended at the first "lazy-seq".

Using the eager next after that, we see two evaluations:

(def y (next x))
 
;=> first lazy-seq evaluated
;=> second lazy-seq evaluated
;=> #'user/y
 
(type y)
 
;=> clojure.lang.Cons
 
(first y)
 
;=> 2

• The first lazy-seq is evaluated, leading to the printout first lazy-seq evaluated
• This results in a nonempty structure: a cons with 1 on the left and a lazy-seq on the right.
• next may have to return nil if the right branch is empty. So we need to check one level deeper.
• The second lazy-seq is evaluated, leading to the printout second lazy-seq evaluated
• This results in a nonempty structure: a cons with 2 on the left and a lazy-seq on the right.
• So don't return nil, return the cons instead.
• When obtaining the first of y, there is nothing do do except retrieve 2 from the already-obtained cons.

Using the lazier rest, we see one evaluation (note that you have to redefine x first to make the this work)

(def y (rest x))
 
;=> first lazy-seq evaluated
;=> #'user/y
 
(type y)
 
;=> clojure.lang.LazySeq
 
(first y)
 
;=> second lazy-seq evaluated
;=> 2

• The first lazy-seq is evaluated, leading to the printout first lazy-seq evaluated
• This results in a nonempty structure: a cons with 1 on the left and a lazy-seq on the right.
• rest never returns nil, even if the lazy-seq on the right would evaluate to the empty seq.
• If the caller needs to know more (is the seq empty?), he can perform the appropriate test later on the lazy-seq.
• So we are done, just return the lazy-seq as result.
• When obtaining the first of y, the lazy-seq needs to be evaluated one step further to obtain the 2

Sidebar

Note that y's type is LazySeq. This may seem obvious, but LazySeq is not at "thing of the language", it is a "thing of the runtime", representing not a result but a state of computation. In fact (type y) being clojure.lang.LazySeq just means "we don't know the type yet, you have to do more to find out". Whenever a Clojure function like nil? hits something that has type clojure.lang.LazySeq, computation will occur!

P.S.

In Joy of Clojure, 2nd edition, on page 126, there is an example using iterate to illustrate the difference between next and rest.

(doc iterate)
;=> Returns a lazy sequence of x, (f x), (f (f x)) etc. f must be free
;   of side-effects

As it turns out, the example doesn't work. In this case, there actually is no difference in the behaviour between next and rest. Not sure why, maybe next knows it won't ever return nil here and just defaults to the behaviour of rest.

(defn print-then-inc [x] (do (print "[" x "]") (inc x)))
 
(def very-lazy (iterate print-then-inc 1))
 
(def very-lazy (rest(rest(rest(iterate print-then-inc 1)))))
;=> [ 1 ][ 2 ]#'user/very-lazy
(first very-lazy)
;=> [ 3 ]4
 
(def less-lazy (next(next(next(iterate print-then-inc 1)))))
;=> [ 1 ][ 2 ]#'user/less-lazy
(first less-lazy)
;=> [ 3 ]4