A sequence is very much like a list: it is an immutable object that can give you its first element or the rest of its elements in constant time. You can also construct a new sequence from an existing sequence and an item to stick at the beginning.

You can test whether something is a sequence using the seq? predicate:

(seq? nil)
;;=> false

(seq? 42)
;;=> false

(seq? :foo)
;;=> false

As you already know, lists are sequences:

(seq? ())
;;=> true

(seq? '(:foo :bar))
;;=> true

Anything you get by calling seq or rseq or keys or vals on a non-empty collection is also a sequence:

(seq? (seq ()))
;;=> false

(seq? (seq '(:foo :bar)))
;;=> true

(seq? (seq []))
;;=> false

(seq? (seq [:foo :bar]))
;;=> true

(seq? (rseq []))
;;=> false

(seq? (rseq [:foo :bar]))
;;=> true

(seq? (seq {}))
;;=> false

(seq? (seq {:foo :bar :baz :qux}))
;;=> true

(seq? (keys {}))
;;=> false

(seq? (keys {:foo :bar :baz :qux}))
;;=> true

(seq? (vals {}))
;;=> false

(seq? (vals {:foo :bar :baz :qux}))
;;=> true

(seq? (seq #{}))
;;=> false

(seq? (seq #{:foo :bar}))
;;=> true

Remember that all lists are sequences, but not all sequences are lists. While lists support peek and pop and count in constant time, in general, a sequence does not need to support any of those functions. If you try to call peek or pop on a sequence that doesn't also support Clojure's stack interface, you'll get a ClassCastException:

(peek (seq [:foo :bar]))
;; java.lang.ClassCastException: clojure.lang.PersistentVector$ChunkedSeq cannot be cast to clojure.lang.IPersistentStack

(pop (seq [:foo :bar]))
;; java.lang.ClassCastException: clojure.lang.PersistentVector$ChunkedSeq cannot be cast to clojure.lang.IPersistentStack

(peek (seq #{:foo :bar}))
;; java.lang.ClassCastException: clojure.lang.APersistentMap$KeySeq cannot be cast to clojure.lang.IPersistentStack

(pop (seq #{:foo :bar}))
;; java.lang.ClassCastException: clojure.lang.APersistentMap$KeySeq cannot be cast to clojure.lang.IPersistentStack

(peek (seq {:foo :bar :baz :qux}))
;; java.lang.ClassCastException: clojure.lang.PersistentArrayMap$Seq cannot be cast to clojure.lang.IPersistentStack

(pop (seq {:foo :bar :baz :qux}))
;; java.lang.ClassCastException: clojure.lang.PersistentArrayMap$Seq cannot be cast to clojure.lang.IPersistentStack

If you call count on a sequence that doesn't implement count in constant time, you won't get an error; instead, Clojure will traverse the entire sequence until it reaches the end, then return the number of elements that it traversed. This means that, for general sequences, count is linear, not constant, time. You can test whether something supports constant-time count using the counted? predicate:

(counted? '(:foo :bar))
;;=> true

(counted? (seq '(:foo :bar)))
;;=> true

(counted? [:foo :bar])
;;=> true

(counted? (seq [:foo :bar]))
;;=> true

(counted? {:foo :bar :baz :qux})
;;=> true

(counted? (seq {:foo :bar :baz :qux}))
;;=> true

(counted? #{:foo :bar})
;;=> true

(counted? (seq #{:foo :bar}))
;;=> false

As mentioned above, you can use first to get the first element of a sequence. Note that first will call seq on their argument, so it can be used on anything "seqable", not just actual sequences:

(first nil)
;;=> nil

(first '(:foo))
;;=> :foo

(first '(:foo :bar))
;;=> :foo

(first [:foo])
;;=> :foo

(first [:foo :bar])
;;=> :foo

(first {:foo :bar})
;;=> [:foo :bar]

(first #{:foo})
;;=> :foo

Also as mentioned above, you can use rest to get a sequence containing all but the first element of an existing sequence. Like first, it calls seq on its argument. However, it does not call seq on its result! This means that, if you call rest on a sequence that contains fewer than two items, you'll get back () instead of nil:

(rest nil)
;;=> ()

(rest '(:foo))
;;=> ()

(rest '(:foo :bar))
;;=> (:bar)

(rest [:foo])
;;=> ()

(rest [:foo :bar])
;;=> (:bar)

(rest {:foo :bar})
;;=> ()

(rest #{:foo})
;;=> ()

If you want to get back nil when there aren't any more elements in a sequence, you can use next instead of rest:

(next nil)
;;=> nil

(next '(:foo))
;;=> nil

(next [:foo])
;;=> nil

You can use the cons function to create a new sequence that will return its first argument for first and its second argument for rest:

(cons :foo nil)
;;=> (:foo)

(cons :foo (cons :bar nil))
;;=> (:foo :bar)

Clojure provides a large sequence library with many functions for dealing with sequences. The important thing about this library is that it works with anything "seqable", not just lists. That's why the concept of a sequence is so useful; it means that a single function, like reduce, works perfectly on any collection:

(reduce + '(1 2 3))
;;=> 6

(reduce + [1 2 3])
;;=> 6

(reduce + #{1 2 3})
;;=> 6

The other reason that sequences are useful is that, since they don't mandate any particular implementation of first and rest, they allow for lazy sequences whose elements are only realized when necessary.

Given an expression that would create a sequence, you can wrap that expression in the lazy-seq macro to get an object that acts like a sequence, but will only actually evaluate that expression when it is asked to do so by the seq function, at which point it will cache the result of the expression and forward first and rest calls to the cached result.

For finite sequences, a lazy sequence usually acts the same as an equivalent eager sequence:

(seq [:foo :bar])
;;=> (:foo :bar)

(lazy-seq [:foo :bar])
;;=> (:foo :bar)

However, the difference becomes apparent for infinite sequences:

(defn eager-fibonacci [a b]
  (cons a (eager-fibonacci b (+' a b))))

(defn lazy-fibonacci [a b]
  (lazy-seq (cons a (lazy-fibonacci b (+' a b)))))

(take 10 (eager-fibonacci 0 1))
;; java.lang.StackOverflowError:

(take 10 (lazy-fibonacci 0 1))
;;=> (0 1 1 2 3 5 8 13 21 34)