Loop, iteration, mapping

Introduction: loop, iterate, for, mapcar, series

loop is the built-in macro for iteration.

Its simplest form is (loop (print "hello")): this will print forever.

A simple iteration over a list is:

(loop for x in '(1 2 3)
  do (print x))

It prints what’s needed but returns nil.

If you want to return a list, use collect:

(loop for x in '(1 2 3)
  collect (* x 10))
;; (10 20 30)

The Loop macro is different than most Lisp expressions in having a complex internal domain specific language that doesn’t use s-expressions. So you need to read Loop expressions with half of your brain in Lisp mode, and the other half in Loop mode. You love it or you hate it.

Think of Loop expressions as having four parts: expressions that set up variables that will be iterated, expressions that conditionally terminate the iteration, expressions that do something on each iteration, and expressions that do something right before the Loop exits. In addition, Loop expressions can return a value. It is very rare to use all of these parts in a given Loop expression, but you can combine them in many ways.

iterate is a popular iteration macro that aims at being simpler, “lispier” and more predictable than loop, besides being extensible. However it isn’t built-in, so you have to import it:

(ql:quickload "iterate")
(use-package :iterate)

Iterate looks like this:

(iter (for i from 1 to 5)
    (collect (* i i)))

(if you use loop and iterate in the same package, you might run into name conflicts)

Iterate also comes with display-iterate-clauses that can be quite handy:

(display-iterate-clauses '(for))
;; FOR PREVIOUS &OPTIONAL INITIALLY BACK     Previous value of a variable
;; FOR FIRST THEN            Set var on first, and then on subsequent iterations
;; ...

Much of the examples on this page that are valid for loop are also valid for iterate, with minor modifications.

for is an extensible iteration macro that is often shorter than loop, that “unlike loop is extensible and sensible, and unlike iterate does not require code-walking and is easier to extend”.

It has the other advantage of having one construct that works for all data structures (lists, vectors, hash-tables…): in doubt, just use for… over:

(for:for ((x over <your data structure>))
   (print …))

You also have to quickload it:

(ql:quickload :for)

We’ll also give examples with mapcar and map, and eventually with their friends mapcon, mapcan, maplist, mapc and mapl which E. Weitz categorizes very well in his “Common Lisp Recipes”, chap. 7. The one you are certainly accustomed to from other languages is mapcar: it takes a function, one or more lists as arguments, applies the function on each element of the lists one by one and returns a list of result.

(mapcar (lambda (it) (+ it 10)) '(1 2 3))
(11 12 13)

map is generic, it accepts list and vectors as arguments, and expects the type for its result as first argument:

(map 'vector (lambda (it) (+ it 10)) '(1 2 3))
;; #(11 12 13)
(map 'list (lambda (it) (+ it 10)) #(1 2 3))
;; (11 12 13)
(map 'string (lambda (it) (code-char it)) '#(97 98 99))
;; "abc"

The other constructs have their advantages in some situations ;) They either process the tails of lists, or concatenate the return values, or don’t return anything. We’ll see some of them.

If you like mapcar, use it a lot, and would like a quicker and shorter way to write lambdas, then you might like one of those lambda shorthand libraries.

Here is an example with cl-punch:

(mapcar ^(* _ 10) '(1 2 3))
;; (10 20 30)

and voilà :) We won’t use this more in this recipe, but feel free to do.

Last but not least, you might like series, a library that describes itself as combining aspects of sequences, streams, and loops. Series expressions look like operations on sequences (= functional programming), but can achieve the same high level of efficiency as a loop. Series first appeared in “Common Lisp the Language”, in the appendix A (it nearly became part of the language). Series looks like this:

(collect
  (mapping ((x (scan-range :from 1 :upto 5)))
    (* x x)))
;; (1 4 9 16 25)

series is good, but its function names are different from what we find in functional languages today. You might like the “Generators The Way I Want Them Generated” library. It is a lazy sequences library, similar to series although younger and not as complete, with a “modern” API with words like take, filter, for or fold, and that is easy to use.

(range :from 20)
;; #<GTWIWTG::GENERATOR! {1001A90CA3}>

(take 4 (range :from 20))
;; (20 21 22 23)

At the time of writing, GTWIWTG is licensed under the GPLv3.

Recipes

Looping forever, return

(loop
    (print "hello"))

return can return a result:

(loop for i in '(1 2 3)
     when (> i 1)
     return i)
2

Looping a fixed number of times

dotimes

(dotimes (n 10)
  (print n))

Here dotimes returns nil. The return value is evaluated at the end of the loop.

You can use return inside of it:

(dotimes (i 10)
   (if (> i 3)
       (return)
       (print i)))

loop… repeat

(loop repeat 10
  do (format t "Hello!~%"))

This prints 10 times “hello” and returns nil.

(loop repeat 10 collect (random 10))
;; (5 1 3 5 4 0 7 4 9 1)

with collect, this returns a list.

Series

(iterate ((n (scan-range :below 10)))
  (print n))

Iterate’s for loop

For lists and vectors:

(iter (for item in '(1 2 3))
  (print item))
(iter (for i in-vector #(1 2 3))
  (print i))

Looping over a hash-table is also straightforward:

(let ((h (let ((h (make-hash-table)))
           (setf (gethash 'a h) 1)
           (setf (gethash 'b h) 2)
           h)))
  (iter (for (k v) in-hashtable h)
    (print k)))
;; b
;; a

In fact, take a look here, or (display-iterate-clauses '(for)) to know about iterating over

symbols in-package
forms - or lines, or whatever-you-wish - in-file, or in-stream
elements in-sequence - sequences can be vectors or lists

Looping over a list

dolist

(dolist (item '(1 2 3))
  (print item))

dolist returns nil.

loop

with in, no surprises:

(loop for x in '(a b c)
      do (print x))
;; A
;; B
;; C
;; NIL

(loop for x in '(a b c)
      collect x)
;; (A B C)

With on, we loop over the cdr of the list:

(loop for i on '(1 2 3) do (print i))
;; (1 2 3)
;; (2 3)
;; (3)

mapcar

(mapcar (lambda (x)
             (print (* x 10)))
         '(1 2 3))
10
20
30
(10 20 30)

mapcar returns the results of the lambda function as a list.

Series

(iterate ((item (scan '(1 2 3))))
  (print item))

scan-sublists is the equivalent of loop for ... on:

(iterate ((i (scan-sublists '(1 2 3))))
  (print i))

Looping over a vector

loop: `across`

(loop for i across #(1 2 3) do (print i))

Series

(iterate ((i (scan #(1 2 3))))
  (print i))

Looping over a hash-table

We create a hash-table:

(setf h (make-hash-table))
(setf (gethash 'a h) 1)
(setf (gethash 'b h) 2)

loop

Looping over keys:

(loop for k being the hash-key of h do (print k))
;; b
;; a

same with hash-value.

Looping over key-values pairs:

(loop for k
    being the hash-key
    using (hash-value v) of h
    do (format t "~a ~a~%" k v))
b 2
a 1

for

the same with for:

(for:for ((it over h))
    (print it))
(A 1)
(B 2)
NIL

maphash

The lambda function of maphash takes two arguments: the key and the value:

(maphash (lambda (key val)
             (format t "key: ~a val:~a~&" key val))
          h)
;; key: A val:1
;; key: B val:2
;; NIL

Series

(iterate (((k v) (scan-hash h)))
  (format t "~&~a ~a~%" k v))

Looping over two lists in parallel

loop

(loop for x in '(a b c)
      for y in '(1 2 3)
      collect (list x y))
;; ((A 1) (B 2) (C 3))

mapcar

(mapcar (lambda (x y)
          (list x y))
        '(a b c)
        '(1 2 3))
;; ((A 1) (B 2) (C 3))

or simply:

(mapcar #'list
        '(a b c)
        '(1 2 3))
;; ((A 1) (B 2) (C 3))

Return a flat list:

(mapcan (lambda (x y)
          (list x y))
        '(a b c)
        '(1 2 3))
;; (A 1 B 2 C 3)

Series

(collect
  (#Mlist (scan '(a b c))
          (scan '(1 2 3))))

A more efficient way, when the lists are known to be of equal length:

(collect
  (mapping (((x y) (scan-multiple 'list
                                  '(a b c)
                                  '(1 2 3))))
    (list x y)))

Return a flat list:

(collect-append ; or collect-nconc
 (mapping (((x y) (scan-multiple 'list
                                 '(a b c)
                                 '(1 2 3))))
   (list x y)))

Nested loops

loop

(loop for x from 1 to 3
      collect (loop for y from 1 to x
		    collect y))
;; ((1) (1 2) (1 2 3))

iterate

(iter outer
   (for i below 2)
   (iter (for j below 3)
      (in outer (collect (list i j)))))
;; ((0 0) (0 1) (0 2) (1 0) (1 1) (1 2))

Series

(collect
  (mapping ((x (scan-range :from 1 :upto 3)))
    (collect (scan-range :from 1 :upto x))))

Computing an intermediate value

Use =.

With for:

(loop for x from 1 to 3
      for y = (* x 10)
      collect y)
;; (10 20 30)

With with, the difference being that the value is computed only once:

(loop for x from 1 to 3
      for y = (* x 10)
      with z = x
      collect (list x y z))
;; ((1 10 1) (2 20 1) (3 30 1))

The HyperSpec defines the with clause like this:

with-clause::= with var1 [type-spec] [= form1] {and var2 [type-spec] [= form2]}*

so it turns out we can specify the type before the = and chain the with with and:

(loop for x from 1 to 3
      for y integer = (* x 10)
      with z integer = x
      collect (list x y z))

(loop for x upto 3
      with foo = :foo
      and bar = :bar
      collect (list x foo bar))

Loop with a counter

loop

Iterate through a list, and have a counter iterate in parallel. The length of the list determines when the iteration ends. Two sets of actions are defined, one of which is executed conditionally.

* (loop for x in '(a b c d e)
      for y from 1

      when (> y 1)
      do (format t ", ")

      do (format t "~A" x)
      )

A, B, C, D, E
NIL

We could also write the preceding loop using the IF construct.

* (loop for x in '(a b c d e)
      for y from 1

      if (> y 1)
      do (format t ", ~A" x)
      else do (format t "~A" x)
      )

A, B, C, D, E
NIL

Series

By iterating on multiple series in parallel, and using an infinite range, we can make a counter.

(iterate ((x (scan '(a b c d e)))
          (y (scan-range :from 1)))
  (when (> y 1) (format t ", "))
  (format t "~A" x))

Ascending, descending order, limits

loop

from… to…:

(loop for i from 0 to 10
      do (print i))
;; 0 1 2 3 4 5 6 7 8 9 10

from… below…: this stops at 9:

(loop for i from 0 below 10
      do (print i))

Similarly, use from 10 downto 0 (10…0) and from 10 above 0 (10…1).

Series

:from ... :upto, including the upper limit:

(iterate ((i (scan-range :from 0 :upto 10)))
  (print i))

:from ... :below, excluding the upper limit:

(iterate ((i (scan-range :from 0 :below 10)))
  (print i))

Steps

loop

with by:

(loop for i from 1 to 10 by 2
      do (print i))

if you use by (1+ (random 3)), the random is evaluated only once, as if it was in a closure:

(let ((step (random 3)))
   (loop for i from 1 to 10 by (+ 1 step)
      do (print i))

Series

with :by

(iterate ((i (scan-range :from 1 :upto 10 :by 2)))
  (print i))

Loop and conditionals

loop

with if, else and finally:

;; https://riptutorial.com/common-lisp/example/11095/conditionally-executing-loop-clauses
(loop repeat 10
      for x = (random 100)
      if (evenp x)
        collect x into evens
      else
        collect x into odds
      finally (return (values evens odds)))

(42 82 24 92 92)
(55 89 59 13 49)

Combining multiple clauses in an if body requires special syntax (and do, and count):

 (loop repeat 10
       for x = (random 100)
       if (evenp x)
          collect x into evens
          and do (format t "~a is even!~%" x)
       else
          collect x into odds
          and count t into n-odds
       finally (return (values evens odds n-odds)))

46 is even!
8 is even!
76 is even!
58 is even!
0 is even!
(46 8 76 58 0)
(7 45 43 15 69)
5

iterate

Translating (or even writing!) the above example using iterate is straight-forward:

(iter (repeat 10)
   (for x = (random 100))
   (if (evenp x)
       (progn
         (collect x into evens)
         (format t "~a is even!~%" x))
       (progn
         (collect x into odds)
         (count t into n-odds)))
   (finally (return (values evens odds n-odds))))

Series

The preceding loop would be done a bit differently in Series. split sorts one series into multiple according to provided boolean series.

(let* ((number (#M(lambda (n) (random 100))
                  (scan-range :below 10)))
       (parity (#Mevenp number)))
  (iterate ((n number) (p parity))
    (when p (format t "~a is even!~%" n)))
  (multiple-value-bind (evens odds) (split number parity)
    (values (collect evens)
            (collect odds)
            (collect-length odds))))

Note that although iterate and the three collect expressions are written sequentially, only one iteration is performed, the same as the example with loop.

Terminate the loop with a test (until, while)

loop

(loop for x in '(1 2 3 4 5)
	until (> x 3)
	collect x)
;; (1 2 3)

the same, with while:

(loop for x in '(1 2 3 4 5)
	while (< x 4)
	collect x)

Series

We truncate the series with until-if, then collect from its result.

(collect
  (until-if (lambda (i) (> i 3))
            (scan '(1 2 3 4 5))))

Loop, print and return a result

loop

do and collect can be combined in one expression

(loop for x in '(1 2 3 4 5)
	while (< x 4)
        do (format t "x is ~a~&" x)
	collect x)
x is 1
x is 2
x is 3
(1 2 3)

Series

By mapping we can perform a side effect and also collect items

(collect
  (mapping ((x (until-if (complement (lambda (x) (< x 4)))
                         (scan '(1 2 3 4 5)))))
    (format t "x is ~a~&" x)
    x))

Named loops and early exit

loop

The special loop named foo syntax allows you to create a loop that you can exit early from. The exit is performed using return-from, and can be used from within nested loops.

;; useless example
(loop named loop-1
    for x from 0 to 10 by 2
    do (loop for y from 0 to 100 by (1+ (random 3))
            when (< x y)
            do (return-from loop-1 (values x y))))
0
2

Loop shorthands for when/return

Several actions provide shorthands for combinations of when/return:

* (loop for x in '(foo 2)
      thereis (numberp x))
T

* (loop for x in '(foo 2)
      never (numberp x))
NIL

* (loop for x in '(foo 2)
      always (numberp x))
NIL

Series

A block is manually created and returned from.

(block loop-1
  (iterate ((x (scan-range :from 0 :upto 10 :by 2)))
    (iterate ((y (scan-range :from 0 :upto 100 :by (1+ (random 3)))))
      (when (< x y)
        (return-from loop-1 (values x y))))))

Count

loop

(loop for i from 1 to 3 count (oddp i))
;; 2

Series

(collect-length (choose-if #'oddp (scan-range :from 1 :upto 3)))

Summation

loop

(loop for i from 1 to 3 sum (* i i))
;; 14

Summing into a variable:

(loop for i from 1 to 3
   sum (* i i) into total
   do (print i)
   finally (print total))
1
2
3
14

Series

(collect-sum (#M(lambda (i) (* i i))
                (scan-range :from 1 :upto 3)))

max, min

loop

(loop for i from 1 to 3 maximize (mod i 3))
;; 2

and minimize.

Series

(collect-max (#M(lambda (i) (mod i 3))
                (scan-range :from 1 :upto 3)))

and collect-min.

Destructuring, aka pattern matching against the list or dotted pairs

loop

(loop for (a b) in '((x 1) (y 2) (z 3))
      collect (list b a) )
;; ((1 X) (2 Y) (3 Z))

(loop for (x . y) in '((1 . a) (2 . b) (3 . c)) collect y)
;; (A B C)

Use nil to ignore a term:

(loop for (a nil) in '((x 1) (y 2) (z 3))
      collect a )
;; (X Y Z)

Iterating 2 by 2 over a list

To iterate over a list, 2 items at a time we use a combination of on, by and destructuring.

We use on to loop over the rest (the cdr) of the list.

(loop for rest on '(a 2 b 2 c 3)
      collect rest)
;; ((A 2 B 2 C 3) (2 B 2 C 3) (B 2 C 3) (2 C 3) (C 3) (3))

We use by to skip one element at every iteration ((cddr list) is equivalent to (rest (rest list)))

(loop for rest on '(a 2 b 2 c 3) by #'cddr
      collect rest)
;; ((A 2 B 2 C 3) (B 2 C 3) (C 3))

Then we add destructuring to bind only the first two items at each iteration:

(loop for (key value) on '(a 2 b 2 c 3) by #'cddr
      collect (list key (* 2 value)))
;; ((A 2) (B 4) (C 6))

Series

In general, with destructuring-bind:

(collect
  (mapping ((l (scan '((x 1) (y 2) (z 3)))))
    (destructuring-bind (a b) l
      (list b a))))

But for alists, scan-alist is provided:

(collect
  (mapping (((a b) (scan-alist '((1 . a) (2 . b) (3 . c)))))
    b))

Custom series scanners

If we often scan the same type of object, we can write our own scanner for it: the iteration itself can be factored out. Taking the example above, of scanning a list of two-element lists, we’ll write a scanner that returns a series of the first elements, and a series of the second.

(defun scan-listlist (listlist)
  (declare (optimizable-series-function 2))
  (map-fn '(values t t)
          (lambda (l)
            (destructuring-bind (a b) l
              (values a b)))
          (scan listlist)))

(collect
  (mapping (((a b) (scan-listlist '((x 1) (y 2) (z 3)))))
    (list b a)))

Shorter series expressions

Consider this series expression:


(collect-sum (mapping ((i (scan-range :length 5)))
                    (* i 2)))

It’s a bit longer than it needs to be—the mapping form’s only purpose is to bind the variable i, and i is used in only one place. Series has a “hidden feature” which allows us to simplify this expression to the following:

(collect-sum (* 2 (scan-range :length 5)))

This is called implicit mapping, and can be enabled in the call to series::install:

(series::install :implicit-map t)

When using implicit mapping, the #M reader macro demonstrated above becomes redundant.

Loop gotchas

the keyword it, often used in functional constructs, can be recognized as a loop keyword. Don’t use it inside a loop.

Appendix: list of loop keywords

Name Clause

named

Variable Clauses

initially finally for as with

Main Clauses

do collect collecting append
appending nconc nconcing into count
counting sum summing maximize return
maximizing minimize minimizing doing
thereis always never if when
unless repeat while until

These don’t introduce clauses:

= and it else end from upfrom
above below to upto downto downfrom
in on then across being each the hash-key
hash-keys of using hash-value hash-values
symbol symbols present-symbol
present-symbols external-symbol
external-symbols fixnum float t nil of-type

But note that it’s the parsing that determines what is a keyword. For example in:

(loop for key in hash-values)

Only for and in are keywords.

Credit and references

Others

See also: more functional constructs (do-repeat, take,…)

Page source: iteration.md

The Common Lisp Cookbook – Loop, iteration, mapping

The Common Lisp Cookbook – Loop, iteration, mapping

Introduction: loop, iterate, for, mapcar, series

Recipes

Looping forever, return

Looping a fixed number of times

dotimes

loop… repeat

Series

Iterate’s for loop

Looping over a list

dolist

loop

mapcar

Series

Looping over a vector

loop: across

Series

Looping over a hash-table

loop

for

maphash

Series

Looping over two lists in parallel

loop

mapcar

Series

Nested loops

loop

iterate

Series

Computing an intermediate value

Loop with a counter

loop

Series

Ascending, descending order, limits

loop

Series

Steps

loop

Series

Loop and conditionals

loop

iterate

Series

Terminate the loop with a test (until, while)

loop

Series

Loop, print and return a result

loop

Series

Named loops and early exit

loop

Loop shorthands for when/return

Series

Count

loop

Series

Summation

loop

Series

max, min

loop

Series

Destructuring, aka pattern matching against the list or dotted pairs

loop

Iterating 2 by 2 over a list

Series

Custom series scanners

Shorter series expressions

Loop gotchas

Appendix: list of loop keywords

Credit and references

Loop

Iterate

Series

Others

loop: `across`