Skip to content
LumenaryAcademy
Practice 60 min

Sequences, laziness and transformation

One abstraction for every collection, infinite sequences computed on demand, threading pipelines and transducers.

Code tested · 4AI-draftedAwaiting review by a computer scientist
MotivationH

One library for all your data

Alan Perlis, the first Turing Award winner, once wrote that it is better to have a hundred functions operating on one data structure than ten functions operating on ten data structures. Clojure takes that advice seriously, with a twist: instead of one data structure, it has one abstraction, the sequence, that every collection can present itself as.

Vectors, lists, maps, sets, strings, Java arrays and collections, lines of a file, rows from a database: all of them can be viewed as a sequence of items, one after another. Learn map, filter, reduce, take, group-by and a few dozen friends once, and they work on all of it. That is why Clojure programs often look like a short pipeline of standard functions, with very little custom looping code.

Sequences in Clojure are also usually lazy: their elements are computed only when someone asks for them. Laziness lets you describe infinite sequences, process data larger than memory one piece at a time, and stop early without wasted work. It also has sharp edges, and this lesson shows both sides.

DefinitionsH

Sequences, laziness and realisation

Definition— Sequence (seq)

A logical list with three operations: first (the first item), rest (a sequence of the remaining items, possibly empty) and cons (a new sequence with an item added at the front). The function seq returns a sequence view of any collection, or nil if the collection is empty.

Definition— Lazy sequence

A sequence whose items are computed on demand and then cached. Creating one does no work; asking for an item realises the sequence up to that point. Most sequence functions in clojure.core (map, filter, take, concat, range and more) return lazy sequences.

Definition— Transducer

A transformation, such as "keep odd numbers" or "square each one", separated from both the input it reads and the output it builds. Transducers compose with comp and can be applied to collections, lazy sequences, channels or streams without creating intermediate sequences. They arrived in Clojure 1.7 (2015).

The abstraction in action

clojure
(prn (seq [1 2 3]) (seq {:a 1 :b 2}) (seq "abc") (seq #{}) (seq nil))
(prn (first "hello") (rest [1 2 3]) (rest [1]) (next [1]))
(prn (cons 0 [1 2 3]) (type (cons 0 [1 2 3])))
(prn (map inc #{10}) (map int "AZ") (reverse "stressed"))
(prn (apply str (reverse "stressed")))
(prn (map vector [:a :b :c] [1 2 3]) (zipmap [:a :b :c] [1 2 3]))
(prn (map + [1 2 3] [10 20 30 40]))
text
(1 2 3) ([:a 1] [:b 2]) (\a \b \c) nil nil
\h (2 3) () nil
(0 1 2 3) clojure.lang.Cons
(11) (65 90) (\d \e \s \s \e \r \t \s)
"desserts"
([:a 1] [:b 2] [:c 3]) {:a 1, :b 2, :c 3}
(11 22 33)
  • A map seen as a sequence is a sequence of entries (key-value vectors); a string is a sequence of characters.
  • (seq coll) returns nil for an empty collection, which makes (if (seq coll) ...) the idiomatic non-empty test.
  • rest of a one-item sequence is the empty sequence (); next returns nil instead. Use rest in lazy code and next when you want a truthiness test.
  • Sequence functions return sequences, not the input type. (reverse "stressed") gives characters; (apply str ...) turns them back into a string. Similarly (map inc #{10}) gives a sequence, not a set. Use into or mapv and filterv when you want a particular collection back.
  • map with several collections walks them in step and stops at the shortest.
IntuitionH

Laziness: describe now, compute later

A lazy sequence is a promise of values. Nothing is computed until something walks it, and walking it computes only as far as needed. This makes infinite sequences ordinary values:

clojure
(prn (take 5 (range)))
(prn (take 6 (iterate #(* 2 %) 1)))
(prn (take 7 (cycle [:red :green])))
(prn (take-while #(< % 30) (map #(* % %) (range))))

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

(prn (take 12 (fib-seq)))
(prn (nth (fib-seq) 90))

(def squares (map (fn [x] (print x "") (* x x)) (range 100)))
(println "defined, nothing computed yet")
(println "\nfirst:" (first squares))
(println "realized?" (realized? squares))
text
(0 1 2 3 4)
(1 2 4 8 16 32)
(:red :green :red :green :red :green :red)
(0 1 4 9 16 25)
(0 1 1 2 3 5 8 13 21 34 55 89)
2880067194370816120
defined, nothing computed yet
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 
first: 0
realized? true

(range) with no arguments counts forever, iterate applies a function again and again, and cycle repeats a collection without end. Each is safe because take and take-while ask for only a finite prefix.

fib-seq shows how to build your own lazy sequence. lazy-seq wraps an expression that produces a sequence and delays evaluating it until the sequence is first used. The recursive call to fib-seq is inside the lazy-seq, so it does not run (and does not overflow the stack) until someone asks for the next element.

The last four lines reveal two important details:

  1. Defining squares printed nothing: no element was computed.
  2. Asking for just the first element computed thirty-two of them. Sequences built from vectors and ranges are chunked: for efficiency, they are realised 32 elements at a time. Laziness in Clojure means "no more than necessary, roughly", not "exactly one element at a time".

That is harmless for pure functions, and it is why you should never rely on laziness to control when side effects happen. A function you pass to map should compute a value, not print, write or send.

Worked examplesH

Pipelines with the threading macros

Nested calls read inside out: (take 3 (sort-by val > (frequencies (re-seq #"[a-z]+" (str/lower-case text))))). The threading macros let you write the same thing as a top-to-bottom pipeline. ->> ("thread last") inserts each result as the last argument of the next form; -> ("thread first") inserts it as the first argument. Sequence functions take the collection last, so pipelines over sequences use ->>; functions on maps such as assoc and update take the map first, so pipelines over a single map use ->.

clojure
(require '[clojure.string :as str])

(def text "The quick fox and the lazy dog; the fox, the dog and the cat.")

(def top-words
  (->> (str/lower-case text)
       (re-seq #"[a-z]+")
       (frequencies)
       (sort-by val >)
       (take 3)))

(prn top-words)

(def orders
  [{:id 1 :city "Lagos"  :total 30}
   {:id 2 :city "Quito"  :total 45}
   {:id 3 :city "Lagos"  :total 25}
   {:id 4 :city "Hanoi"  :total 60}
   {:id 5 :city "Quito"  :total 15}])

(prn (-> (first orders) (assoc :status :shipped) (update :total * 2)))

(prn (->> orders
          (group-by :city)
          (map (fn [[city os]] [city (reduce + (map :total os))]))
          (into (sorted-map))))

(prn (partition 2 [1 2 3 4 5]) (partition-by even? [2 4 1 3 6]))
(prn (mapcat (fn [n] (repeat n n)) [1 2 3]) (keep #(when (odd? %) (* % 10)) [1 2 3]))
(prn (for [x (range 1 4) y [:a :b] :when (odd? x)] [x y]))
text
(["the" 5] ["fox" 2] ["and" 2])
{:id 1, :city "Lagos", :total 60, :status :shipped}
{"Hanoi" 60, "Lagos" 55, "Quito" 60}
((1 2) (3 4)) ((2 4) (1 3) (6))
(1 2 2 3 3 3) (10 30)
([1 :a] [1 :b] [3 :a] [3 :b])

Walk through the word count. Lower-case the text; re-seq returns a lazy sequence of every regular-expression match; frequencies counts each distinct item into a map; sort-by val > orders the entries by count, largest first; take 3 keeps the top three. Words with equal counts (here "fox", "and" and "dog" each appear twice) keep whatever order frequencies produced, so a real program would add a tie-breaker.

Example— Debugging a pipeline one step at a time

Pipelines are easy to inspect because every intermediate value is plain data. When top-words gives a surprising answer, evaluate a shorter pipeline at the REPL: cut it after the step you doubt and look.

clojure
(->> (str/lower-case text) (re-seq #"[a-z]+") (take 4))
;; => ("the" "quick" "fox" "and")

(->> (str/lower-case text) (re-seq #"[a-z]+") frequencies)
;; => {"the" 5, "quick" 1, "fox" 2, "and" 2, "lazy" 1, "dog" 2, "cat" 1}

Now the tie is visible: three words have a count of 2, and which two of them make the top three depends on the map's internal order. Fix it by sorting on a compound key, count descending and then the word alphabetically. juxt builds that key as a vector, and vectors compare element by element:

clojure
(->> (str/lower-case text)
     (re-seq #"[a-z]+")
     (frequencies)
     (sort-by (juxt (comp - val) key))
     (take 3))
;; => (["the" 5] ["and" 2] ["dog" 2])

Two small tools make this style of debugging faster. The reader macro #_ tells Clojure to ignore the next form entirely, so you can switch off one step of a pipeline without deleting it: (->> [3 1 2] #_(map inc) (sort)) gives (1 2 3). And because each step is an ordinary function call, any step can be copied out and tested on its own with a hand-written input.

The order totals use group-by, which builds a map from each key (here the result of calling :city on an order) to the vector of items with that key, and then pour the result into a sorted-map to get a predictable order.

A few more functions you will use weekly:

FunctionWhat it does
partition n collsplit into groups of n, dropping an incomplete last group (partition-all keeps it)
partition-by f collstart a new group whenever f's result changes
mapcat f collmap, then concatenate the results
keep f collmap, then drop the nil results
fora list comprehension: nested iteration with :when, :while and :let, returning a lazy sequence
reduce-kvreduce over a map's keys and values without building entry vectors
distinct, deduperemove all duplicates, remove consecutive duplicates

Misconception

"for is a loop." In Clojure, for builds a lazy sequence; it is not a statement that runs its body. A for used for printing at the top level does nothing, just like map. Use doseq (same syntax) for side effects.

Worked examplesH

Transducers: transformations without the collections

A ->> pipeline creates an intermediate lazy sequence at every step: filter builds one, map builds another from it. For most code that cost is irrelevant. For hot paths, and for data that is not a sequence at all (a stream of messages, a channel), Clojure offers transducers. Calling map, filter, take and most other sequence functions without a collection returns a transducer, and transducers compose with comp:

clojure
(def xform
  (comp (filter odd?)
        (map #(* % %))
        (take 4)))

(prn (into [] xform (range 100)))
(prn (transduce xform + (range 100)))
(prn (sequence xform (range 100)))

(def clean-names
  (comp (map clojure.string/trim)
        (remove empty?)
        (map clojure.string/capitalize)
        (distinct)))

(prn (into [] clean-names ["  amara " "" "KENJI" "amara" " sofia"]))
(prn (into #{} clean-names ["ana" "Ana " "ANA"]))
text
[1 9 25 49]
84
(1 9 25 49)
["Amara" "Kenji" "Sofia"]
#{"Ana"}

Note the order: with transducers, comp reads left to right in the order the data flows (filter, then square, then take), the same as a ->> pipeline. That surprises people who know that comp of ordinary functions applies right to left; it falls out of how transducers wrap one another.

  • into applies a transducer while pouring into a collection.
  • transduce applies it while reducing: here, summing the first four odd squares, 1 + 9 + 25 + 49 = 84.
  • sequence gives a lazy sequence; eduction gives a reusable, recomputed view.
  • clean-names is a reusable recipe: defined once, applied to a vector or a set, with no intermediate collections. clojure.string/trim is written fully qualified here because no alias was required; the namespace is loaded with Clojure itself.

Transducers do the whole pipeline in a single pass, element by element, so (take 4) stops the work as soon as four squares are found, without chunking.

ComputationC

The costs of laziness

Laziness is not free, and experienced Clojure programmers know where it bites.

Holding the head. A lazy sequence caches what it has realised. If you keep a reference to the beginning of a huge sequence while walking to its end, every realised element stays in memory. (let [xs (map parse (line-seq rdr))] (println (count xs) (first xs))) keeps all lines alive, because first needs xs after count has walked it. Compute what you need in one pass, or restructure so the head is not retained.

Infinite sequences and eager functions. (count (range)) never returns, and printing an infinite sequence at the REPL tries to print forever (set *print-length* to protect yourself).

Resources that close too soon. A lazy sequence of lines read inside with-open will be realised after the file is closed if it escapes the block, raising an exception. Realise it inside with doall, vec or into, or do all the work inside the block.

Stacked laziness. Repeatedly wrapping a sequence in concat thousands of times ((reduce concat ...)) builds a deep tower of unrealised thunks that overflows the stack when finally walked. Use into or mapcat instead.

The usual cure for all four is the same: be eager where laziness buys nothing. mapv, filterv, into, reduce, run! and transducers are all eager, and modern Clojure style reaches for them more often than older code did.

ExplanationH

How professionals use sequences

  • Pipelines first. Most data processing in Clojure is a ->> pipeline of core functions. When a step has no name in the core library, write a small, named function for it rather than an anonymous blob, so the pipeline still reads like a sentence.
  • Eager at the edges. Return vectors (via mapv, into or vec) from functions whose results are stored, printed or passed across a boundary, so callers never inherit unrealised work or delayed exceptions.
  • No side effects in lazy code. Logging, I/O and changes to state go in doseq, run! or reduce, not in map.
  • Transducers for reusable or hot transformations. A transducer like clean-names can be tested on a vector in the REPL and then used unchanged on a stream in production.
  • Know the cheatsheet. A surprising amount of Clojure expertise is simply knowing that partition-by, frequencies, group-by, reductions, interleave or split-with exists. Reading the official cheatsheet once a month for your first year pays off.
Exercises

Exercises

1. Sequences, laziness and transformation

Warm-upComputational

What does this print?

(prn (seq []) (rest [1]) (next [1]))

2. Sequences, laziness and transformation

Warm-upComputational

What does this expression return?

(->> (range 10)
     (filter even?)
     (map #(* % %))
     (reduce +))

3. Sequences, laziness and transformation

CoreComputational

What does this print?

(prn (-> 5 (- 2) (* 10))
     (->> 5 (- 2) (* 10)))

4. Sequences, laziness and transformation

StretchComputational

How many dots does this program print?

(def xs (map #(do (print ".") %) (range 1000)))
(first xs)

5. Sequences, laziness and transformation

Warm-upComputational

What does this print?

(prn (take 5 (iterate #(+ % 3) 1)))

6. Sequences, laziness and transformation

CoreComputational

What does this print?

(prn (partition-by odd? [1 3 2 4 5]))

7. Sequences, laziness and transformation

CoreComputational

What does (into [] (comp (filter even?) (map inc)) [1 2 3 4]) return?

Choose one

8. Sequences, laziness and transformation

StretchHuman

A function opens a file with with-open, returns (map parse-line (line-seq rdr)) from inside the block, and its caller then prints the result. What happens?

Choose one

Further reading and resources

  • SequencesThe official reference for the seq abstraction and the sequence library.
  • Laziness in ClojureHow lazy sequences are built and realised.
  • TransducersThe official reference for composable transformations, added in Clojure 1.7.
  • Clojure cheatsheetThe "Seq in, Seq out" and "Using a Seq" sections are this lesson in one page.