CLJ file format: Sequences and laziness

Clojure defines many algorithms in terms of sequences (seqs). A seq is a logical list: unlike a Lisp cons cell, the ISeq interface lets many data structures offer their elements as a sequence. (seq coll) returns a seq on the collection, or nil if it is empty. Most functions of the sequence library are lazy: they return their result a little at a time as it is consumed, and consume their input the same way.

The seq interface

Function	Result
`(seq coll)`	a seq, or `nil` when the collection is empty or `nil`. Works on collections, strings, arrays, `Iterable`s and maps (a seq of map entries)
`(first coll)`	the first item (`nil` for an empty collection); calls `seq`
`(rest coll)`	the items after the first; for no more items, an empty logical sequence (never `nil`)
`(next coll)`	like `rest`, but `nil` when there are no more items
`(cons item seq)`	a new seq with `item` in front

Because the empty seq is logically true but (seq …) of it is nil, the idiom for testing for more items is (when (seq xs) …). A seq taken from a Java Iterable is a persistent, single pass over the data; because the pass may happen lazily it can see changes made after seq was called.

Laziness

(lazy-seq body) delays the body, which must return a seq (or nil); it is run once, the first time the seq is looked at, and the result is cached. It is the way to write a function that returns a lazy seq, and allows infinite sequences: (defn nums [n] (lazy-seq (cons n (nums (inc n))))).
rest returns a possibly empty tail without finding out whether anything follows, and next returns nil for an empty one, which needs the following item to be looked at. The design notes on laziness in the reference explain that this split lets sequences be fully lazy.
lazy-cat concatenates lazily. delay and force (and realized?) give the same effect for a single value.
Sequences over vectors, ranges, and many library results are processed in chunks of up to 32 items for speed, so a lazy seq may compute a little more than was asked (chunk-first, chunk-rest, chunk-cons, chunked-seq? and friends are the low-level interface).
doall realises a whole lazy seq and returns it; dorun realises it and returns nil; doseq walks one for side effects. Side effects inside map run only when the result is consumed.
Holding on to the head of a long lazy seq keeps all realised items in memory; the code that creates a seq should not keep a reference to its start while another consumes it.

The sequence library

Purpose	Functions
shorter seq from a longer one	`distinct` `filter` `remove` `for` `keep` `keep-indexed` `dedupe` `random-sample` `take-nth`
longer seq from a shorter one	`cons` `concat` `lazy-cat` `mapcat` `cycle` `interleave` `interpose` `repeat` `repeatedly` `iterate` `range`
head items missing	`rest` `next` `fnext` `nnext` `drop` `drop-while` `nthnext` `nthrest` `for`
tail items missing	`take` `take-nth` `take-while` `butlast` `drop-last` `for`
rearrange	`flatten` `reverse` `sort` `sort-by` `shuffle` `group-by` `partition-by` `frequencies`
nested seqs	`split-at` `splitv-at` `split-with` `partition` `partitionv` `partition-all` `partitionv-all` `partition-by`
process each item	`map` `pmap` `mapcat` `map-indexed` `for` `replace` `seque`
using a seq	`seqable?` `first` `second` `last` `ffirst` `nfirst` `nth` `peek` `rand-nth` `some` `every?` `not-every?` `not-any?` `empty?` `count` `bounded-count` `identical?`
construct a collection from a seq	`zipmap` `into` `reduce` `reduce-kv` `reductions` `set` `vec` `into-array` `to-array` `mapv` `filterv`
pass the items as arguments	`apply`
create a seq	`list` `vector` `seq` `vals` `keys` `rseq` `subseq` `rsubseq` `sequence` `line-seq` `file-seq` `tree-seq` `xml-seq` `re-seq` `iterator-seq` `enumeration-seq` `resultset-seq` `stream-seq!`

reduce (and reduce-kv, reductions) works over a collection directly, calling the function with an accumulator and each item, and reduced stops it early. Since Clojure 1.7 most of these functions return a transducer when the collection argument is left out.

(defn fib-seq
  ([] (fib-seq 0 1))
  ([a b] (lazy-seq (cons a (fib-seq b (+ a b))))))

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

(->> (range) (filter odd?) (map #(* % %)) (take 5))
;; => (1 9 25 49 81)

An infinite lazy sequence, and a pipeline of lazy steps of which only five items are computed.

Not described

Known, not yet covered

Reference: the full argument lists and edge cases of each function (partition padding, iterate and iteration, reductions and the reducers library clojure.core.reducers, the fork-join fold) are not described; the sequence reference page was read for its function groups.

Unknown

Reference: the chunk size of 32 is from memory of the implementation and was not checked in the source.

.CLJ File Format – Sequences and laziness