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 `cons`truct 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)
``````