Beyond single values
Functions let us abstract over a single value, but real data comes in bulk. What happens when we want to transform every element of a collection at once?
Consider incrementing each number in the vector [1 2 3]. The function inc expects a number, not a vector, so we need a different strategy. One option is to reach in and grab each element individually with nth, apply inc, and piece the results back together.
user=> (def numbers [1 2 3])
#'user/numbers
user=> (nth numbers 0)
1
user=> (inc (nth numbers 0))
2
user=> (inc (nth numbers 1))
3
user=> (inc (nth numbers 2))
4
user=> [(inc (nth numbers 0)) (inc (nth numbers 1)) (inc (nth numbers 2))]
[2 3 4]
That works for a three-element vector, but it breaks for a two-element one:
user=> (def numbers [1 2])
#'user/numbers
user=> [(inc (nth numbers 0)) (inc (nth numbers 1)) (inc (nth numbers 2))]
IndexOutOfBoundsException clojure.lang.PersistentVector.arrayFor (PersistentVector.java:107)
Attempting to access index 2 of numbers throws an “index out of bounds” because the vector only holds indices 0 and 1. We could trim the expression, but then we'd be editing the code for every different vector length — a non-starter for thousands of elements.
The recursive way
Let's shrink the problem. Can we increment just the first element of a vector and reattach it? The first function gets the lead element; rest returns everything else. To glue them back together, use cons, which builds a new sequence from an element and an existing sequence.
user=> (first [1 2 3])
1
user=> (rest [1 2 3])
(2 3)
user=> (cons 1 [2])
(1 2)
user=> (cons 1 [2 3])
(1 2 3)
user=> (cons 1 [2 3 4])
(1 2 3 4)
(defn inc-first [nums]
(cons (inc (first nums))
(rest nums)))
user=> (inc-first [1 2 3 4])
(2 2 3 4)
But what about an empty vector? There is no first element to increment.
user=> (inc-first [5])
(6)
user=> (inc-first [])
NullPointerException clojure.lang.Numbers.ops (Numbers.java:942)
user=> (first [])
nil
user=> (inc nil)
NullPointerException clojure.lang.Numbers.ops (Numbers.java:942)
We need a conditional. Clojure's if handles two cases: when the sequence is empty, return an empty sequence; otherwise, increment the first element and leave the rest alone.
user=> (doc if)
-------------------------
if
(if test then else?)
Special Form
Evaluates test. If not the singular values nil or false,
evaluates and yields then, otherwise, evaluates and yields else. If
else is not supplied it defaults to nil.
Please see http://clojure.org/special_forms#if
user=> (if true :a :b)
:a
user=> (if false :a :b)
:b
(defn inc-first [nums]
(if (first nums)
; If there's a first number, build a new list with cons
(cons (inc (first nums))
(rest nums))
; If there's no first number, just return an empty list
(list)))
user=> (inc-first [])
()
user=> (inc-first [1 2 3])
(2 2 3)
Now notice something about the non-empty branch: it already applies the operation to (rest nums), which is itself a sequence of numbers. If we apply the same function to that sub-sequence, we'll process its own first element as well.
(defn inc-more [nums]
(if (first nums)
(cons (inc (first nums))
(inc-more (rest nums)))
(list)))
user=> (inc-more [1 2 3 4])
(2 3 4 5)
That single change increments every element, not just the first. Here's why: the function keeps calling itself on smaller and smaller rests. Eventually, (rest [4]) yields an empty sequence, the if takes the false branch, and evaluation stops.
We can think of this as unfolding into a chain of cons calls:
(cons 2 (cons 3 (cons 4 (cons 5 '()))))
(cons 2 (cons 3 (cons 4 '(5))))
(cons 2 (cons 3 '(4 5)))
(cons 2 '(3 4 5))
'(2 3 4 5)
This pattern is recursion, and two key pieces keep it working:
- A base case with a known answer: incrementing every element of an empty sequence just returns an empty sequence.
- A recurrence relation connecting the problem to a smaller version of itself: increment the first element, then increment the rest.
The if binds those cases together into a self-referential function. Once the base case is established, each subsequent step reduces the problem until only one call remains.
user=> (inc-more [1 2 3 4 5 6 7 8 9 10 11 12])
(2 3 4 5 6 7 8 9 10 11 12 13)
Generalizing the transformation
Nothing about the recursive solution depends on inc. We can parameterize over any function f:
(defn transform-all [f xs]
(if (first xs)
(cons (f (first xs))
(transform-all f (rest xs)))
(list)))
Instead of numbers only, the function accepts any sequence. It works for incrementing numbers:
user=> (transform-all inc [1 2 3 4])
(2 3 4 5)
…for converting strings to keywords:
user=> (transform-all keyword ["bell" "hooks"])
(:bell :hooks)
…and for wrapping elements in lists:
user=> (transform-all list [:codex :book :manuscript])
((:codex) (:book) (:manuscript))
This concept — relating each element of a sequence to each element of another — is fundamental. In Clojure, it's the function map:
user=> (map inc [1 2 3 4])
(2 3 4 5)
Note the distinction: the function map transforms one sequence into another by applying a function element-wise. The type named map — is a dictionary relating keys to values — may be sparse and arbitrarily complex, while the function typically expresses a single consistent relationship along a fixed ordering.
Growing sequences
Recursion also expands any single value into a sequence of successive applications of some function to itself. Here's an example:
(defn expand [f x count]
(when (pos? count)
(cons x (expand f (f x) (dec count)))))
The base case is nil when count hits zero. Each call produces x, then recurses on (f x) with a decremented count, yielding a list: x, (f x), (f (f x)), and so on. Starting from 0 with inc:
user=> user=> (expand inc 0 10)
(0 1 2 3 4 5 6 7 8 9)
Clojure generalizes this with iterate, which yields an infinite sequence and pairs well with take:
user=> (take 10 (iterate inc 0))
(0 1 2 3 4 5 6 7 8 9)
More elaborate seeds and functions stretch its reach:
user=> (take 10 (iterate (fn [x] (if (odd? x) (+ 1 x) (/ x 2))) 10))
(10 5 6 3 4 2 1 2 1 2)
user=> (take 5 (iterate (fn [x] (str x "o")) "y"))
("y" "yo" "yoo" "yooo" "yoooo")
repeat builds a sequence where every element is the same, while repeatedly generates values by calling a zero-argument function over and over — handy for random data:
user=> (take 10 (repeat :hi))
(:hi :hi :hi :hi :hi :hi :hi :hi :hi :hi)
user=> (repeat 3 :echo)
(:echo :echo :echo)
user=> (rand)
0.9002678382322784
user=> (rand)
0.12375594203332863
user=> (take 3 (repeatedly rand))
(0.44442397843046755 0.33668691162169784 0.18244875487846746)
Note that functions like rand return different results each call, making them impure: they cannot be replaced by a constant value.
For numeric ranges, use range: (range n) produces the integers 0 through n-1; (range n m) steps from n to m-1; and (range n m step) skips by a given increment.
user=> (range 5)
(0 1 2 3 4)
user=> (range 2 10)
(2 3 4 5 6 7 8 9)
user=> (range 0 100 5)
(0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95)
And cycle repeats a sequence endlessly:
user=> (take 10 (cycle [1 2 3]))
(1 2 3 1 2 3 1 2 3 1)
Joining and reshaping
map also accepts multiple sequences. Given several, it calls the function with one element from each collection in turn, stopping when the smallest runs out. Think of it as a zipper:
user=> (map (fn [n vehicle] (str "I've got " n " " vehicle "s"))
[0 200 9]
["car" "train" "kiteboard"])
("I've got 0 cars" "I've got 200 trains" "I've got 9 kiteboards")
user=> (map + [1 2 3]
[4 5 6]
[7 8 9])
(12 15 18)
To pair each element with its index, combine a finite sequence with the infinite range, or use the dedicated map-indexed:
user=> (map (fn [index element] (str index ". " element))
(iterate inc 0)
["erlang" "ruby" "haskell"])
("0. erlang" "1. ruby" "2. haskell")
user=> (map-indexed (fn [index element] (str index ". " element))
["erlang" "ruby" "haskell"])
("0. erlang" "1. ruby" "2. haskell")
You can concatenate sequences with concat, or riffle them with interleave. To place a fixed element between every adjacent pair, use interpose:
user=> (concat [1 2 3] [:a :b :c] [4 5 6])
(1 2 3 :a :b :c 4 5 6)
user=> (interleave [:a :b :c] [1 2 3])
(:a 1 :b 2 :c 3)
user=> (interpose :and [1 2 3 4])
(1 :and 2 :and 3 :and 4)
To reverse the order, call reverse. Strings are sequences of characters, so the same tools apply; the sequence functions and apply str rebuild strings from character sequences:
user=> (reverse [1 2 3])
(3 2 1)
user=> (reverse "woolf")
(\f \l \o \o \w)
user=> (apply str (reverse "woolf"))
"floow"
user=> (seq "sato")
(\s \a \t \o)
For randomized order, shuffle works as expected:
user=> (shuffle [1 2 3 4])
[3 1 2 4]
user=> (apply str (shuffle (seq "abracadabra")))
"acaadabrrab"
Selecting pieces
take selects the first n elements; drop discards them. The pair take-last and drop-last work at the tail:
user=> (range 10)
(0 1 2 3 4 5 6 7 8 9)
user=> (take 3 (range 10))
(0 1 2)
user=> (drop 3 (range 10))
(3 4 5 6 7 8 9)
user=> (take-last 3 (range 10))
(7 8 9)
user=> (drop-last 3 (range 10))
(0 1 2 3 4 5 6)
The -while variants (take-while, drop-while) cut based on a predicate:
user=> (take-while pos? [3 2 1 0 -1 -2 10])
(3 2 1)
And split-at dichotomizes at an index while split-with splits via a predicate:
(split-at 4 (range 10))
[(0 1 2 3) (4 5 6 7 8 9)]
user=> (split-with number? [1 2 3 :mark 4 5 6 :mark 7])
[(1 2 3) (:mark 4 5 6 :mark 7)]
Since indices begin at zero, the functions align predictably: (split-at 4) puts exactly four elements first, and the second half begins at index 4; (range 10) holds ten elements for indices 0–9.
To keep only certain elements, filter retains those for which a predicate returns a truthy value, while remove keeps the rest:
user=> (filter pos? [1 5 -4 -7 3 0])
(1 5 3)
user=> (remove string? [1 "turing" :apple])
(1 :apple)
For grouping, partition and relatives divide sequences into chunks — e.g., collecting alternating values into pairs:
user=> (partition 2 [:cats 5 :bats 27 :crocodiles 0])
((:cats 5) (:bats 27) (:crocodiles 0))
Or splitting runs of negatives versus positives individually:
(user=> (partition-by neg? [1 2 3 2 1 -1 -2 -3 -2 -1 1 2])
((1 2 3 2 1) (-1 -2 -3 -2 -1) (1 2))
Collapsing a Sequence
After transforming a sequence, we often want to collapse it into something smaller. Counting how many times each element appears is one common case:
user=> (frequencies [:meow :mrrrow :meow :meow])
{:meow 3, :mrrrow 1}
Grouping elements by a function is another. Here, :first is used as a keyword function to extract first names, and group-by builds a map from each first name to the list of people sharing it:
user=> (pprint (group-by :first [{:first "Li" :last "Zhou"}
{:first "Sarah" :last "Lee"}
{:first "Sarah" :last "Dunn"}
{:first "Li" :last "O'Toole"}]))
{"Li" [{:last "Zhou", :first "Li"} {:last "O'Toole", :first "Li"}],
"Sarah" [{:last "Lee", :first "Sarah"} {:last "Dunn", :first "Sarah"}]}
The most general way to collapse a sequence is reduce. Unlike map, which treats each element in isolation, reducing carries state along. The function f receives (f state element) and returns the next state. The final state becomes the return value of reduce:
user=> (doc reduce)
-------------------------
clojure.core/reduce
([f coll] [f val coll])
f should be a function of 2 arguments. If val is not supplied,
returns the result of applying f to the first 2 items in coll, then
applying f to that result and the 3rd item, etc. If coll contains no
items, f must accept no arguments as well, and reduce returns the
result of calling f with no arguments. If coll has only 1 item, it
is returned and f is not called. If val is supplied, returns the
result of applying f to val and the first item in coll, then
applying f to that result and the 2nd item, etc. If coll contains no
items, returns val and f is not called.
With (reduce + [1 2 3 4]), the process begins with (+ 1 2) returning 3, then (+ 3 3) returning 6, then (+ 6 4) returning 10. You can think of it as inserting the function between every pair of elements:
1 + 2 + 3 + 4
3 + 3 + 4
6 + 4
10
To see intermediate states, reductions returns a sequence of all of them:
user=> (reductions + [1 2 3 4])
(1 3 6 10)
Often we supply an initial default state. For example, start with an empty set and add each element as you go:
user=> (reduce conj #{} [:a :b :b :b :a :a])
#{:a :b}
Reducing elements into a collection is common enough to have its own name: into. You can conj [key value] vectors into a map, or build a list:
user=> (into {} [[:a 2] [:b 3]])
{:a 2, :b 3}
user=> (into (list) [1 2 3 4])
(4 3 2 1)
Because conj prepends to a list, this reverses the sequence. Vectors append to the end, so to preserve order while reducing:
user=> (reduce conj [] [1 2 3 4 5])
(reduce conj [] [1 2 3 4 5])
[1 2 3 4 5]
That looks a lot like map—all that’s missing is a transformation on each element:
(defn my-map [f coll]
(reduce (fn [output element]
(conj output (f element)))
[]
coll))
user=> (my-map inc [1 2 3 4])
[2 3 4 5]
So map is a special case of reduce. What about take-while? The reduced function signals an early completion, skipping the rest of the sequence:
(defn my-take-while [f coll]
(reduce (fn [out elem]
(if (f elem)
(conj out elem)
(reduced out)))
[]
coll))
Reduce really does underpin almost any sequence operation. That said, Clojure’s built-in functions aren’t all written that way. take-while, for instance, is actually defined recursively:
user=> (source take-while)
(defn take-while
"Returns a lazy sequence of successive items from coll while
(pred item) returns true. pred must be free of side-effects."
{:added "1.0"
:static true}
[pred coll]
(lazy-seq
(when-let [s (seq coll)]
(when (pred (first s))
(cons (first s) (take-while pred (rest s)))))))
The lazy-seq construct defers computation until the result is required, so most of Clojure’s sequence functions are lazy. You can increment numbers up to infinity, and the call returns immediately because nothing has been evaluated yet. The sequence is unrealized:
user=> (def infseq (map inc (iterate inc 0)))
#'user/infseq
user=> (realized? infseq)
false
Once accessed, the elements are computed on demand, and lazy sequences also remember their contents for faster subsequent access.
Bringing It Together
Let’s solve a more complex problem with these tools: sum the products of consecutive pairs from the first 1000 odd integers.
Start with the integers, and take just the first 10 to keep things printable:
user=> (take 10 (iterate inc 0))
(0 1 2 3 4 5 6 7 8 9)
Filter out the odds:
user=> (take 10 (filter odd? (iterate inc 0)))
(1 3 5 7 9 11 13 15 17 19)
For consecutive pairs, partition initially gives non-overlapping pairs—not what we want. Adding the step parameter fixes that:
user=> (take 3 (partition 2 1 (filter odd? (iterate inc 0))))
((1 3) (3 5) (5 7))
Multiply each pair with map:
user=> (take 3 (map (fn [pair] (* (first pair) (second pair)))
(partition 2 1 (filter odd? (iterate inc 0)))))
(3 15 35)
Finally, sum the products, adjusting the take to 1000:
user=> (reduce +
(take 1000
(map (fn [pair] (* (first pair) (second pair)))
(partition 2 1
(filter odd?
(iterate inc 0)))))
1335333000
The expression works, but reads inside-out: the part that happens first is deepest in the nesting. A thread-last macro, ->>, flattens the flow so each step reads from top to bottom:
user=> (->> 0
(iterate inc)
(filter odd?)
(partition 2 1)
(map (fn [pair]
(* (first pair) (second pair))))
(take 1000)
(reduce +))
1335333000
That reads much more naturally—each function applies to the previous result. How ->> manages to do this without a second argument for take is a mystery for another chapter: macros.
Problems
- Write a function that tests whether a string is a palindrome—the same forwards and backwards.
- Count the number of “c”s in “abracadabra”.
- Write your own version of
filter. - Find the first 100 prime numbers: 2, 3, 5, 7, 11, 13, 17, ….
