Some / rest vs. next

looking at the code for clj some on github:
https://github.com/clojure/clojure/blob/master/src/clj/clojure/core.clj

(defn some
  "Returns the first logical true value of (pred x) for any x in coll,
  else nil.  One common idiom is to use a set as pred, for example
  this will return :fred if :fred is in the sequence, otherwise nil:
  (some #{:fred} coll)"
  {:added "1.0"
   :static true}
  [pred coll]
    (when-let [s (seq coll)]
      (or (pred (first s)) (recur pred (next s)))))

why not use rest instead of next?

2 Likes

They are quite similar, but next looks at the result of the “next” thing (so it may be evaluated) and returns nil, while rest just returns the “next” thing. So usually next is better, but IRL they might be equivalent.

next and rest only differ in how they respond to an empty sequence, next returns nil, rest returns an empty list. (in particular: clojure.lang.PersistentList/EMPTY).

on the next iteration seq would return nil either way, but it needs to do more work in the second case. It would have to call the seq method on that empty list, which then returns nil.

(.seq clojure.lang.PersistentList/EMPTY) ;;=> nil

So next is the more basic option.

1 Like

Thanks for the explanation. Do you have an example of when rest should be used instead?

Also, welcome, @taf! Good first question, thanks for asking.

hmmm… so here is next

(def
 ^{:arglists '([coll])
   :tag clojure.lang.ISeq
   :doc "Returns a seq of the items after the first. Calls seq on its
  argument.  If there are no more items, returns nil."
   :added "1.0"
   :static true}  
 next (fn ^:static next [x] (. clojure.lang.RT (next x))))

so i follow along to the java code

static public ISeq next(Object x){
	if(x instanceof ISeq)
		return ((ISeq) x).next();
	ISeq seq = seq(x);
	if(seq == null)
		return null;
	return seq.next();
}

so does that not mean that (next s) is really (seq (rest s))? and if so, does that not mean that rest would be more appropriate for some?

These are the implementations for next and rest (in clojure.lang.RT called more)

static public ISeq next(Object x){
	if(x instanceof ISeq)
		return ((ISeq) x).next();
	ISeq seq = seq(x);
	if(seq == null)
		return null;
	return seq.next();
}

static public ISeq more(Object x){
	if(x instanceof ISeq)
		return ((ISeq) x).more();
	ISeq seq = seq(x);
	if(seq == null)
		return PersistentList.EMPTY;
	return seq.more();
}

As you can see the only difference is what happens when seq == null.

Honestly I’m not sure, I always have a hard time remembering which is which to begin with. Given that Clojure is quite systematic with its nil-punning they are usually interchangeable.

Looking at clojure.core it seems Rich uses rest a few times when passing the result to map or concat, which kind of makes sense because you clearly expect something seqable there, but OTOH map and concat will start by calling seq first, so next would work just fine and might even be a tiny tad faster.

Does anyone have a rule of thumb of when to use which one, or even how to remember which is which? :slight_smile: :thinking:

1 Like

So rest always returns a sequence, whereas next returns nil rather than an empty sequence. I learned something today!

user=> (rest [1])
()
user=> (next [1])
nil

I’ve previously just used (rest xs) in my own code, even when iterating. But with next, I’ll be able to to that more smoothly! I re-implemented map (no lazyness) with this logic, which let me avoid some null checks.

I tried re-implementing map with both, and the next version was 20 % faster. Didn’t expect that!

(defn- map-next*
  [f xs]
  (if xs
    (cons (f (first xs))
          (map-next* f (next xs)))))

(defn map-next
  "Map with next"
  [f xs]
  (map-next* f (seq xs)))

(map-next (partial * 10) (range 10))
;; => (0 10 20 30 40 50 60 70 80 90)

(defn map-rest
  "Map with rest"
  [f xs]
  (if (seq xs)
    (cons (f (first xs))
          (map-rest f (rest xs)))))

(map-rest (partial * 10) (range 10))
;; => (0 10 20 30 40 50 60 70 80 90)


(time
 (do (prn :timing/map-next)
     (repeatedly 10000
             #(map-next (partial * 10)
                        (range 100)))
     :done))
"Elapsed time: 0.577231 msecs"

(time
 (do (prn :timing/map-rest)
     (repeatedly 10000
                 #(map-rest (partial * 10)
                            (range 100)))
     :done))
"Elapsed time: 0.793458 msecs"
1 Like

first of all i want to thank everyone for answering my question so quickly!

nevertheless i have to say that i am still very much confused about seq, rest and next :frowning:

now in order to explain where all of this confusion is coming from, i should perhaps say, that i have read the book ‘the joy of clojure, 2nd edition’ ( or at least large parts of it ) and to be honest i still think that it is a fantastic book. having said that, i now feel like i may have taken some things from the book without doing sufficient testing on my own.

so for example in my mind (next s) was really like (seq (rest s)) and also i took away from the book, that rest is more lazy than next.

so then i just happened to write a piece of code that used the some function, and sometimes i do look at the source from clojure itself so i found that it did use the seq check for the condition but then also next for the recursive part. so i thought to myself, well is that not like calling seq too often?

so i thought well, why not register at clojureverse and ask about this, and i am really
glad i did, because the answers that i got made me realize, that some of the preconceived ideas i had formed because of the book i mentioned, really do need some re-evaluation.

alright, so first of all i did search for the topics of seq, next and rest in the book again
( with manning you do get the pdf version as well, so that came in really handy!)… in any
case in the book you find for example under chapter 3.2 ‘nil pun with care’ the following:

(defn print-seq [s]
  (when (seq s)
    (prn (first s))
    (recur (rest s))))

and then it goes on to say:

Second, rest is used instead of next to consume the sequence on the recursive call.
Although they’re nearly identical in behavior, rest can return a sequence that’s either
empty or not empty (has elements) C , but it never returns nil . On the other hand,
next returns a seq of the rest , or (seq (rest s)) , and thus never returns an empty
sequence, returning nil in its place. It’s appropriate to use rest here because you’re
using seq explicitly in each subsequent iteration.

also under chapter 6.3.2 ‘Understanding the lazy-seq recipe’ there is a little box
titled next vs. rest in which you can find the following code example:

(def very-lazy (-> (iterate #(do (print .) (inc %)) 1)
rest rest rest))
;=> …#'user/very-lazy
(def less-lazy (-> (iterate #(do (print .) (inc %)) 1)
next next next))
;=> …#'user/less-lazy

so i tried that out as well BUT!!! it did not come out as expected. and
it seams i was not the only one to notice this:

now in the comments i found:

I would think the advice would stand because next is still one item less lazy than rest. – webappzero Nov 3 '17 at 20:58

but i have a really hard time to even come up with a good example for showing this difference in lazy behavior.

so… some, seq, rest, next??? clojure idiom for doing nil-pun iteration like stuff,… i am
totally lost!

if anyone could help shed some more light on this matter i would really
appriciate it, because it seams to me that the matter at hand is pretty
important, since it seams so basic,…

1 Like

As that SO answer says, the definition of iterate changed between Clojure 1.6 and 1.7. If you look at the behavior of the 1.6 version of iterate, you see the difference in laziness:

user=> (defn iter [f x] (cons x (lazy-seq (iter f (f x)))))
#'user/iter
user=> (def very-lazy (-> (iter #(do (print \.) (inc %)) 1) rest rest rest))
..#'user/very-lazy ; only two dots here
user=> (def less-lazy (-> (iter #(do (print \.) (inc %)) 1) next next next))
...#'user/less-lazy ; three dots here
user=> (println (first very-lazy))
.4 ; forces one more iteration
nil
user=> (println (first less-lazy))
4 ; that iteration had already been done
nil
user=> 

Does that help?

1 Like

yes, thanks!

although i am not yet 100% sure about what is going on with some, seq, rest and next… i am sure it will come to me :slight_smile:

…how about…

(defn some-loop [pred coll]
  (loop [s (seq coll)]
    (when s
      (or (pred (first s)) (recur (next s))))))

so i did also ask on ask.clojure.org about this, ( https://ask.clojure.org/index.php/8361/changing-some ) since the people who actually work on clj itself read those posts, and so alexmiller pointed out the following to me:
( https://ask.clojure.org/index.php/4220/reduce-based-some )

so i wanted to try some stuff out by making a few minor changes to the test code from petterik

(ns checksome.core
  (:require [criterium.core :as cc]
            [clojure.pprint :as pp])
  (:gen-class))

;;  compiling: lein uberjar
;;  running: java -Xmx3g "-Dclojure.compiler.direct-linking=true" -server -jar checksome-0.1.0-SNAPSHOT-standalone.jar

(defn some-as-is
  {:static true}
  [pred coll]
  (when-let [s (seq coll)]
    (or (pred (first s)) (recur pred (next s)))))

(defn some-as-is-coll
  {:static true}
  [pred coll]
  (when (seq coll)
    (or (pred (first coll)) (recur pred (next coll)))))

(defn some-reduce-reduced
  {:static true}
  [pred coll]
  (reduce (fn [_ x]
            (when-let [ret (pred x)]
              (reduced ret)))
          nil
          coll))

(defn some-loop
  {:static true}
  [pred coll]
  (loop [s (seq coll)]
    (when s
      (or (pred (first s)) (recur (next s))))))

(defn some-rest
  {:static true}
  [pred coll]
  (when-let [s (seq coll)]
    (or (pred (first s)) (recur pred (rest s)))))

(defn some-rest-coll
  {:static true}
  [pred coll]
  (when (seq coll)
    (or (pred (first coll)) (recur pred (rest coll)))))

(def i (iterate inc 0))
(def r (range 1e5))
(def v (into [] r))
(def s (doall (map inc r)))
(def st (into (sorted-set) r))

(defn benchmark-mean [benchmark]
  (let [estimate (:mean benchmark)
        mean (first estimate)
        [factor unit] (cc/scale-time mean)]
    (cc/format-value mean factor unit)))

(defn run-bench [dry-run?]
  (let [pred #(< 1e4 %)
        fns {:some-as-is  some-as-is
             :some-as-is-coll  some-as-is-coll
             :some-reduce-reduced  some-reduce-reduced
             :some-loop  some-loop
             :some-rest  some-rest
             :some-rest-coll some-rest-coll}
        results (doall
                 (for [[coll-key coll] {:iterate  i
                                        :range    r
                                        :vector   v
                                        :lazy-seq s
                                        :set      st}]
                   (if dry-run?
                     (mapv #((val %) pred coll) fns)
                     (into {:coll coll-key}
                           (map (fn [[fn-key f]]
                                  (let [mean
                                        (benchmark-mean
                                         (cc/with-progress-reporting
                                           (cc/benchmark* #(f pred coll)
                                                                nil)))]
                                    [fn-key mean])))
                           fns))))]
    (when-not dry-run?
      (pp/print-table [:coll
                       :some-as-is
                       :some-as-is-coll
                       :some-reduce-reduced
                       :some-loop
                       :some-rest
                       :some-rest-coll]
                      results))))

(comment ;; Run through everything with a dry run to warm everything up.
  (run-bench true)
  ;; Run everything again.
  (run-bench false)
  ;; Prints
  "|-----------+--------------+--------------|"
  "|     :coll |   :core-some |    :new-some |"
  "|-----------+--------------+--------------|"
  "|  :iterate | 14.502145 ms |  3.994055 ms |"
  "|    :range | 16.949429 ms | 14.903065 ms |"
  "|   :vector | 23.706839 ms |  5.765865 ms |"
  "| :lazy-seq | 28.723150 ms |  5.616475 ms |"
  "|      :set | 53.063608 ms | 17.419191 ms |"
  "|-----------+--------------+--------------|"
  )

(defn -main [& args]
  (run-bench true)
  (run-bench false))

and i got:

|     :coll |   :some-as-is | :some-as-is-coll | :some-reduce-reduced |    :some-loop |    :some-rest | :some-rest-coll |
|-----------+---------------+------------------+----------------------+---------------+---------------+-----------------|
|  :iterate | 167.732258 µs |    182.555152 µs |         77.668439 µs | 145.891641 µs | 335.996220 µs |   337.987755 µs |
|    :range | 161.825047 µs |    418.207479 µs |        245.045011 µs | 384.698539 µs | 518.020047 µs |   447.564067 µs |
|   :vector | 546.941943 µs |    553.703470 µs |         27.337982 µs | 511.788287 µs | 583.460261 µs |   585.360362 µs |
| :lazy-seq | 626.275314 µs |    625.262426 µs |         79.271493 µs | 588.170668 µs | 626.238351 µs |   645.487925 µs |
|      :set |   1.997573 ms |      2.036398 ms |        265.132762 µs |   1.940083 ms |   1.879984 ms |     1.899150 ms |

also here is the project.clj:

(defproject checksome "0.1.0-SNAPSHOT"
  :description "FIXME: write description"
  :url "http://example.com/FIXME"
  :license {:name "EPL-2.0 OR GPL-2.0-or-later WITH Classpath-exception-2.0"
            :url "https://www.eclipse.org/legal/epl-2.0/"}
  :dependencies [[org.clojure/clojure "1.10.0"]
                 [criterium "0.4.5"]]
  :main ^:skip-aot checksome.core
  :target-path "target/%s"
  :profiles {:uberjar {:aot :all}})

also:

java -version
openjdk version "11.0.4" 2019-07-16
OpenJDK Runtime Environment (build 11.0.4+11-post-Ubuntu-1ubuntu218.04.3)
OpenJDK 64-Bit Server VM (build 11.0.4+11-post-Ubuntu-1ubuntu218.04.3, mixed mode, sharing)

now i still have to think about many of the things involved, ( i find that this does raise a lot of very interesting questions :-))… so i really can not say much about what this means,… but i guess i just wanted to keep anyone interested in this ‘in the loop’ :slight_smile:

As a non-answer to this question, I’d recommend having a look at

which in many ways serves as the idea for the reducers library in Clojure.