Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 36 ยท Sequences and Laziness

The Sequence Abstraction

Understand Clojure's sequence abstraction: seq, first, rest, next, cons and conj, and why one set of functions works on lists, vectors, maps, sets and strings.

Most languages give every collection its own set of methods. Clojure does something different: it defines one small abstraction, the sequence, and writes hundreds of functions against it. map, filter, take, reduce and sort do not care whether you hand them a list, a vector, a map, a set, a string or a Java array. They ask the collection for a sequence view of itself and work through that.

This lesson explains the three primitives behind the abstraction, how collections become sequences, and the difference between conj and cons. The next lessons build on it: lazy sequences, transducers and everyday sequence functions.

Clojure itself does not run in the site's code editors. The Clojure snippets below are read-only, and each runnable example is a small JavaScript stand-in that mimics the same idea so you can experiment with it.

Three primitives: seq, first, rest

The sequence abstraction is defined by three functions:

  • (seq coll) returns a sequence over coll, or nil if the collection is empty.
  • (first s) returns the first item, or nil if there is none.
  • (rest s) returns everything after the first item, as a sequence. It never returns nil; when nothing is left you get an empty sequence.
CLOJURE
(first [10 20 30])   ;=> 10
(rest  [10 20 30])   ;=> (20 30)
(seq [])             ;=> nil
(rest [10])          ;=> ()

Notice that rest on a vector gives you a sequence, not a vector. You are looking at the vector through a sequence window. The vector itself is not changed (Clojure's data is immutable by default, so nothing ever is).

There is a sibling, next, that behaves like rest except that it returns nil for "nothing left" instead of an empty sequence:

CLOJURE
(rest [1])   ;=> ()
(next [1])   ;=> nil

That one difference matters for loops. Because nil is falsey and () is truthy, the standard idiom for walking a sequence is (when-let [s (seq coll)] ...): seq converts an empty collection to nil, so the test ends the walk.

CLOJURE
(defn count-items [coll]
  (loop [s (seq coll) n 0]
    (if s
      (recur (next s) (inc n))
      n)))

(count-items "hello")        ;=> 5
(count-items {:a 1 :b 2})    ;=> 2

Strings, maps and sets all work, because seq knows how to adapt each of them.

Everything seqable

A collection is seqable when seq can turn it into a sequence. The built-in seqables are:

Collection What seq yields
list, vector the elements in order
map key/value pairs, each a two-element vector
set the members (order unspecified)
string characters
Java arrays, Iterables the elements
nil nil (so nil acts as an empty collection)
CLOJURE
(seq {:a 1 :b 2})   ;=> ([:a 1] [:b 2])
(seq "abc")         ;=> (\a \b \c)
(map inc #{1 2 3})  ;=> (2 3 4)   ; order may differ

Because maps yield pairs, you can destructure each entry directly in a function: (map (fn [[k v]] ...) m). That is why (into {} (map (fn [[k v]] [k (* v 2)]) m)) is a common way to transform a map.

The practical payoff is large: you learn about 70 sequence functions once and apply them to every data structure. When a function needs an "empty" result it typically returns an empty sequence, not an empty version of the original type, so use into when you must get a vector or set back: (into [] (filter even? #{1 2 3 4})).

Seq of a seq is the same seq

Calling seq on something that is already a sequence returns the sequence unchanged. This is what makes sequence functions composable: (map inc (filter odd? (range 10))) simply passes sequences from one function to the next. The functions that consume a sequence call seq on their argument, and the ones that produce one return a sequence, so the whole pipeline fits together without conversions.

Adding items: conj vs cons

Two functions add an item, and they behave differently.

  • (cons x coll) always returns a sequence with x at the front, whatever coll was.
  • (conj coll x) adds x in the way that is cheapest for that collection, and returns the same kind of collection.
CLOJURE
(cons 0 [1 2 3])   ;=> (0 1 2 3)   a seq
(conj [1 2 3] 4)   ;=> [1 2 3 4]   adds at the END of a vector
(conj '(1 2 3) 0)  ;=> (0 1 2 3)   adds at the FRONT of a list
(conj #{1 2} 3)    ;=> #{1 2 3}
(conj {:a 1} [:b 2]) ;=> {:a 1, :b 2}

A list is a singly linked chain, so the front is cheap. A vector is an indexed tree where the end is cheap. conj hides this: you ask for "add an item" and the collection chooses the right spot. Use conj for building collections and cons when you specifically want to prepend to a sequence, as in a recursive lazy producer.

How a linked sequence works

Under the surface a sequence is a head plus "the rest", the same shape as a classic linked list. The diagram shows (cons 0 [1 2 3]): a new cell is created and the existing items are reused, not copied.

flowchart LR
  A["cons cell: 0"] --> B["rest: seq over [1 2 3]"]
  B --> C["1"]
  B --> D["2"]
  B --> E["3"]

Prepending creates one new cell and shares the rest. This sharing is called structural sharing, and it is what makes immutable data fast.

Try it: first, rest and next

JavaScript has no seq, but we can imitate the three primitives with generators. Notice how the rule "rest never returns nothing, next does" shows up in the code.

JS first, rest, next in JavaScript

Press Run (or Ctrl + Enter) to see the console output here.

No output.

conj vs cons in a stand-in

This second stand-in models a vector (add at the end) and a list (add at the front) to show why conj picks the position for you.

JS conj picks the cheap end

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Common mistakes

  • Testing emptiness with (= x ()). Use (empty? x) or the seq idiom, which is also correct for nil.
  • Expecting a vector back. (map f [1 2 3]) returns a sequence. Wrap with vec or into [] when you need indexed access.
  • Using cons to build a vector. cons always yields a sequence; use conj.
  • Counting on map order. Small maps keep insertion order, but do not rely on it; sort explicitly when order matters.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does (rest [1]) return?

    rest never returns nil; with nothing left it returns an empty sequence. next is the one that returns nil.
  2. 2. What does (seq []) return?

    seq returns nil for an empty collection, which is why (when-let [s (seq coll)] ...) ends loops cleanly.
  3. 3. Which call returns a vector?

    conj keeps the collection type. cons, rest and map all return sequences.
  4. 4. Why does (conj '(1 2 3) 0) add at the front?

    conj adds at the cheapest position of each collection: the front of a list, the end of a vector.

Summary

  • A sequence is defined by seq, first and rest; hundreds of functions are written against it.
  • Lists, vectors, maps, sets, strings, arrays and nil are all seqable.
  • rest returns an empty sequence, next returns nil, and seq turns empty into nil.
  • conj adds in the natural place and keeps the type; cons prepends and returns a sequence.
  • Use into to turn a sequence result back into a vector, set or map.

Next: Lazy Sequences