lisp

Iteration in Lisp

Common Lisp provide many iteration-related macros, but their usages often confuse beginners. So I think it the time to write an introduction to Lisp iteration/loop.

In Emacs Lisp, the following function/macro are also available, but (require 'cl) first is necessary.

Contents

1. while
2. mapcar/mapc/map
3. dolist
4. dotimes
5. do
6. loop
7. Example: Fractorial

#while

(while TEST BODY...)

1
2
3
4
5
6
7
8
9
10
11
12
13
(let ((i 0))
  (while (< i 5)
    (princ i)
    (incf i)))
;; => 01234nil
;; note: nil is the return-value of `while' itself. 01234 is the side-effect of princ.
 
(let ((i 0) result)
  (while (< i 5)
    (setq result (concat result (format "%s, " i)))
    (incf i))                           ;equal to (setq i (1+ i))
  result)
;;=> "0, 1, 2, 3, 4, "
  1. While TEST in non-nil, eval BODY…
  2. Repeat until TEST is nil.

mapcar/mapc/map

A list as input argument is required.

(mapcar FUNCTION SEQUENCE)
(mapc FUNCTION SEQUENCE)
(map TYPE FUNCTION SEQUENCE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(mapcar (lambda (x)
          (* x x))
        '(1 2 3 4 5))
;; => (1 4 9 16 25)

(mapcar #'1+ '(1 2 3 4 5))  ; #'1+ is a function
;; => (2 3 4 5 6)

(mapc (lambda (x)
        (* x x))
      '(1 2 3 4 5))
;; => (1 2 3 4 5)

(map 'list (lambda (x) (* x x)) '(1 2 3 4 5))
;; => (1 4 9 16 25)

(map 'vector (lambda (x) (* x x)) '(1 2 3 4 5))
;; => [1 4 9 16 25]

SEQUENCE: may be a list/vector/bool-vector/string

  1. Apply a FUNCTION to each element of SEQUENCE.
  2. mapcar and map collect all results (of FUNCTION) into a list and return it.
  3. map can sqecify output SEQUENCE type but mapcar can’t.
  4. mapc just for side-effect, and it always return the original list. That’s to say, you have to do what you want in lambda body, e.g. (push (* x x) output-list).

You can also use map/mapcar like this:

1
2
3
4
(mapcar #'cons '(1 2 3) '(a b c))
;; => ((1 . a) (2 . b) (3 . c))
(mapcar #'list '(1 2 3) '(a b c) '("Apple" "Banana" "Citrus"))
;; => ((1 a "Apple") (2 b "Banana") (3 c "Citrus"))

Notice: In Emacs Lisp, use mapcar* instead; otherwise, mapcar cannot accept multiple sequences.

#dolist

A list as input argument is required.

(dolist (VAR LIST [RESULT]) BODY...)

1
2
3
4
5
6
7
8
9
(dolist (x '(1 2 3 4 5))
  (princ x))
;; => 12345nil
;; note: nil is the return-value of dolist itself.
 
(let (result)
  (dolist (x '("a" "b" "c" "d" "e") (format "Output is %s" result)) ; (VAR LIST RESULT)
    (setq result (concat result x ", "))))
;; => "Output is a, b, c, d, e, "
  1. Default return-value is nil, but you can specify RESULT as its return-value.
  2. It’s only available with a LIST.

dotimes

(dotimes (VAR COUNT [RESULT]) BODY...)

1
2
3
4
(dotimes (i 5)
  (princ i))
;; => 01234nil
;; note: nil is the return-value of `dotimes' itself. 01234 is the "side-effect" of princ.
  1. Count from 0. e.g. (dotimes (i 5) ...), i= 0, 1, 2, 3, 4
  2. Same as dolist, Used for side-effect.
  3. Default return-value is nil, but you can specify it in RESULT.

do

(do ((VAR INIT [STEP])...)
    (END-TEST [RESULT...])
    BODY...)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(do ((i 0 (1+ i))) ; (VAR INIT [STEP])
    ((= i 5))      ; (END-TEST)
  (princ i))
;; => 01234nil

(do ((a 0 (1+ a))  ; (VAR INIT [STEP])
     (b 5 (1- b))) ; (VAR INIT [STEP])
    ((= b 0))      ; (END-TEST)
  (princ (list a b)))
;; => (0 5)(1 4)(2 3)(3 2)(4 1)nil
;; note: lists are the "side-effect" of `princ'. nil is the return-value of `do' itself.
;; (Because we doesn't add RESULT, its return-value is nil.)


;; Now let's add RESULT argument:
(do ((a 0 (1+ a))           ; ((VAR INIT [STEP])
     (b 5 (1- b)))          ;  (VAR INIT [STEP]))
    ((= b 0) (vector a b))  ; (END-TEST [RESULT...])
  (princ (list a b))
  )
;; => (0 5)(1 4)(2 3)(3 2)(4 1)[5 0]
  1. Multiple variables (VAR) is acceptable, and they will update their values by eval STEP after each iteration.
  2. Default return-value is nil, but you can specify it in RESULT.
  3. End the loop when END-TEST is non-nil, and eval RESULT as return-value of do.

loop

“How Lisp loop macro works?” “Magic.”

loop is the most complexe iteration macro in Lisp. It’s very powerful, but before playing with it, a lot of “keywords” and rules needed to be memorized and comprehended first. Following merely noted some most frequently used keywords and their usages:

for + from/to/below/above/downto

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(loop for i from 0 to 5 do (princ i)) ;; "do" won't return anything; so return-value of loop itself is nil.
;; => 012345nil

;; "Collect" results into a list (like `mapcar'/`map')
(loop for i from 1 to 5 collect (* i i)) ;"collect" all results of (* i i) into a list as `loop's return-value
;; => (1 4 9 16 25)

;; for + from/to/below/above/downto
(loop for i from 3 to 10 collect i)
;; => (3 4 5 6 7 8 9 10)
(loop for i to 10 collect i)
;; => (0 1 2 3 4 5 6 7 8 9 10)
(loop for i below 10 collect i)
;; => (0 1 2 3 4 5 6 7 8 9)

(loop for i from 10 above 0 collect i)
;; => (10 9 8 7 6 5 4 3 2 1)
(loop for i from 10 downto 0 collect i)
;; => (10 9 8 7 6 5 4 3 2 1 0)

for + in/across

in is easy to understand, it just traverse over all elements in LIST.
across is used on ARRAY/VECTOR

1
2
3
4
5
6
7
8
9
10
11
;; for + in LIST
(loop for x in '("Apple" "Banana" "Citrus") collect (concat x " is fruit."))
;; => ("Apple is fruit." "Banana is fruit." "Citrus is fruit.")

;; for + across ARRAY/VECTOR
(loop for x across ["Apple" "Banana" "Citrus"] collect (concat x " is fruit."))
;; => ("Apple is fruit." "Banana is fruit." "Citrus is fruit.")

;; Multiple VARs
(loop for (x y) in '((2 3) (4 5) (6 7)) collect (+ x y))
;; => (5 9 13)

in/on

on is a little strange, which traverse over all cons cells of the LIST.

1
2
(loop for x on '("Apple" "Banana" "Citrus") collect x)
;; => (("Apple" "Banana" "Citrus") ("Banana" "Citrus") ("Citrus"))

repeat/while

1
2
3
;; repeat n times
(loop repeat 3 do (princ "Hello!"))     ;return-value of loop itself is nil.
;; => Hello!Hello!Hello!nil

do itself won’t return anything.

collect/append/sum/count/maximize/minimize

usages are similiar to collect.

  • count FORM count the times when FORM is non-nil.
  • You can use into to save the value into a variable.
1
2
3
4
5
6
7
8
9
10
(loop for i from 1 to 100
      minimize i)
=> 1

(loop for i from 1 to 100
      sum i into SUM
      count (and (>= i 11) (eq (% i 11) 0)) into MULTIPLE-OF-11
      maximize i into MAX
      finally return (format "sum: %s, multiples of 11: %s, max: %s" SUM MULTIPLE-OF-11 MAX))
;; => "sum: 5050, multiples of 11: 9, max: 100"

when/if

1
2
3
4
5
6
7
8
9
10
11
12
13
;; Note: `when' is just a synonym for `if'
(loop for i from 1 to 10
      when (oddp i) collect i into x
      finally return x)
      => (1 3 5 7 9)
      
(loop for i from 1 to 10
      when (oddp i)
        collect i into x
      else
        collect i into y
        finally return (vector x y))
=> [(1 3 5 7 9) (2 4 6 8 10)]

finally

finally [do] FORMS... and finally return FORM will execute FORM after the whole loop is done.

for/with

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
;; `for VAR =` to set VAR at every iterates.
(loop for a from 1 to 10
      for b = (* a a)
      collect (list a b))
;; => ((1 1) (2 4) (3 9) (4 16) (5 25) (6 36) (7 49) (8 64) (9 81) (10 100))

;; `with VAR =` to set VAR, but leave it alone during the loop.
(loop for a from 1 to 10
      with b = (* a a)
      collect (list a b))
;; => ((1 1) (2 1) (3 1) (4 1) (5 1) (6 1) (7 1) (8 1) (9 1) (10 1))

;; so if you want, add a `do` to update `b` every loop
(loop for a from 1 to 10
      with b = (* a a)
      do (setq b (* a a))
      collect (list a b))
;; => ((1 1) (2 4) (3 9) (4 16) (5 25) (6 36) (7 49) (8 64) (9 81) (10 100))

always/never

Return value of loop would be t or nil.

1
2
3
4
5
6
7
(loop for size in '(12 11 14 8)
      always (> size 10))
=> nil

(loop for size in '(12 11 14 15)
      always (> size 10))
=> t

More loop Examples

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
(let ((n 1))
  (loop do (set 'n (* n 2)) until (> n 100) collect n))
;; => (2 4 8 16 32 64)

(let ((n 1))
  (loop do (set 'n (* n 2)) until (> n 100) finally return n))
;; => 128

(loop for x from 1
      for y = (* x x)
      until (> y 50)
      finally return y)
;; => 64

;; Get a random integer from 1 to 5
(loop for x = (random 6) when (> x 0) return x)

;; and & then
(loop for x below 5
      for y = nil then x
      collect (list x y))
;; => ((0 nil) (1 1) (2 2) (3 3) (4 4))

(loop for x below 5
      and y = nil then x
      collect (list x y))
;; => ((0 nil) (1 0) (2 1) (3 2) (4 3))

Example: Fractorial

Read code is more comprehensible than explianation in text.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
;; recursive
(defun frac (n)
  (if (<= n 1)
      1
    (* n (frac (1- n)))))

;; while
(defun frac (n)
  (if (<= n 1)
      1
    (let ((fin n))
      (while (> n 1)
        (incf n -1)
        (setq fin (* fin n)))
      fin)))

;; dotimes
(defun frac (n)
  (if (<= n 1)
      1
    (let (fin)
      (dotimes (x n)
        (push (1+ x) fin))
      (apply #'* fin))))

;; do
(defun frac (n)
  (if (<= n 1)
      1
    (do ((i 2 (1+ i))
         (fin 1))
        ((> i n) fin)
      (setq fin (* fin i)))))

;; loop
(defun frac (n)
  (if (<= n 1)
      1
    (apply #'*
           (loop for i from 1 to n
                 collect i))))

(defun frac (n)
  (if (<= n 1)
      1
    (loop for i from 1 to n
          for x = 1 then (* x i)
          finally return x)))

;; mapcar (dirty hack, do not try this stupid way)
(defun frac (n)
  (if (<= n 1)
      1
    (apply #'*
           (progn
             (incf n)
             (mapcar
              (lambda (nonsense) (incf n -1))
              (make-list (1- n) nil))))
    ))