Clojure sequences and collections

Question

In Lisp all data structures builds of cons cells, i.e they are essentially linked lists or binary trees or both (correct me if I'm wrong). Clojure data structures are lists, vectors, maps and sets. Clojure incorporates two inclusive abstractions for these data structures: collections and sequences. Sequence abstraction defines first, rest and cons operations, where as collection abstraction define collection specific operations such as conj and into.

Clojure core functions such as map and filter operates on sequence abstraction but accepts any data structure and performs implicit conversion. These functions are also lazy. Does this mean by default Clojure internally stores data in more efficient data structures such as indexed arrays and only switches to linked lists as needed? How does Clojure actually convert collections to sequences? Is the sequence built from collection using iterator in a streaming fashion or as a whole and then passed to the consumer?

Answer 1

The only data structure in Clojure that is a singly-linked list is an actual list like:

(list 1 2 3)

Everything else is an efficient data structure (i.e. vector, map).

A lazy-sequence is (nominally) composed of the current value and a recipe for generating the next value. Once computed, elements are cached and are not re-computed.

Conversion of a collection to a sequence is an implementation detail and is not normally important to the end user.

The original map and filter functions are lazy, as are many others. However, this was enough of a headache (unpredictable time of realization) that eager/imperative versions mapv and filterv were added to the language.