Common Lisp学习笔记（十一）

11 Iteration and Block Structure

11 Iteration and Block Structure

11.2 dotimes and dolist

dotimes和dolist都是macro func

(dotimes (index-var n [result-form])
  body)

(dolist (index-var list [result-form])
  body)

dotimes执行n次body，index-var从0加到n - 1. 如果参数有result-form则最后返回它的值，如果没有则返回nil

dolist用法相同，只是index-var改成一个list,迭代完list中的元素

> (dotimes (i 4) (format t "count ~S~&" i))
count 1
count 2
count 3
count 4
nil

> (dolist (x '(red blue green) 'flowers)
    (format t "~&roses are ~S" x))
roses are red
roses are blue
roses are green
flowers

11.2 exiting the body of a loop return可以从loop中返回，return只有一个参数就是要返回的值

(defun find-first-odd (list-of-numbers)
  (dolist (e list-of-numbers)
    (format t "~&testing ~S..." e)
    (when (oddp e)
      (format t "found an odd number.")
      (return e))))

ex 11.1

(defun it-member (x y)
  (dolist (e y nil)
    (if (equal x e) (return t))))

ex 11.2

(defun it-assoc (x y)
  (dolist (e y nil)
    (if (equal x (first e)) (return e))))

ex 11.3

(defun check-all-odd (list-of-numbers)
  (cond ((null list-of-numbers) t)
        (t (format t "~&checking ~S" (first list-of-numbers))
           (unless (evenp (first list-of-numbers))
                (check-all-odd (rest list-of-numbers))))))

11.4 recursive, iterative

当在一个简单的list上进行i遍历的时候，使用iterative可以更加简单的遍历这个list,有几个原因：1.dolist可以自动判断list是否结束，而递归需要使用cond写明终止条件 2.在迭代中使用e就可以访问list中的每个元素，而递归的时候则要小心注意每次要(first list)来访问第一个元素，然后使用(rest list)来缩小范围

但是也有很多情况使用递归会更加方便。首先递归的方法很容易理解，将问题描述得非常清楚。如在遍历tree的结构的时候，使用递归可以很简单，但是用迭代的方法来遍历树的结构需要加非常多的条件判断和控制等。

ex 11.4

(defun it-length (x)
  (let ((result 0)) 
    (dolist (e x result)
        (incf result))))

ex 11.5

(defun it-nth (n x)
  (dotimes (i n (first x))
    (pop x)))

ex 11.6

(defun it-union (x y)
  (let ((result nil))
    (dolist (e x)
        (unless (member e result) (push e result)))
    (dolist (e y result)
        (unless (member e result) (push e result)))))

(defun it-union (x y)
  (dolist (e x y)
    (unless (member e y) (push e y))))

11.6 比较dolist, mapcar, recursion

mapcar是对一个list的每个元素都使用一个func操作的最简单的方式

比如要计算一个list的所有元素的平方

(defun app-square-list (list-of-numbers)
  (mapcar #'(lambda (n) (* n n)) list-of-numbers))

(defun rec-square-list (x) 
  (cond ((null x) nil)
        (t (cons (* (first x) (first x))
                 (rec-square-list (rest x))))))

迭代的方式虽然不像递归要注意结束条件的判断，但是要用不断使用显式赋值来得到结果

(defun it-square-list (list-of-numbers)
  (let ((result nil))
    (dolist (e list-of-numbers (reverse result))
        (push (* e e) result))))

返回的结果要加一个reverse，因为每次是把当前计算的平方push到result的末尾，所以得到的list是倒过来的

ex 11.8

(defun it-reverse (x)
  (let ((result nil))
    (dolist (e x result)
        (push e result))))

11.7 DO macro

(do ((var1 init1 [update1])
     (var2 init2 [update2])
     ...)
    (test action1 action2 actionn)
    body)

do是lisp中最强大的迭代函数，它可以：

绑定任意数量的变量，像let
自己定义每一步的step长度
自己定义何时跳出循环的测试

首先，var list中的变量会初始化为init的值，然后判断test，如果为t，则对后面的所有action求值，并返回最后一个的值。如果为nil，则进入body，执行所有的body语句。在body中可以加入return指令直接结束do函数。执行完body后会回到var list中更新var的值，每个var会更新为[update]中得到的值，如果没有该update则该var保持不变。接着继续执行test判断是进入action还是body. do只要test为真就会进入action执行然后就会结束

eg,

(defun launch (n)
  (do ((cnt n (- cnt 1)))
      ((zerop cnt) (format t "blast off!"))
      (format t "~S..." cnt)))

ex 11.9

(defun check-all-odd (x)
  (do ((e x (rest e)))
      ((null e) t)
      (format t "~&checking ~S..." (first e))
      (if (evenp (first e)) (return nil))))

ex 11.10

(defun launch (n)
  (dotimes (i n)
    (format t "~S..." (- n i)))
  (format t "blast off"))

11.8 隐式赋值的好处

do与dotimes和dolist相比有很多好处：

可以定义每一步的变化长度，也可以到过来计数
do可以绑定多个变量，并在更新变量的时候完成隐式赋值，因此不需要使用一些显式的setf或者let，push，因此可以写出很优雅的代码

使用do的求阶乘函数

(defun fact (n)
  (do ((i n (- i 1))
       (result 1 (* result i)))
      ((zerop i) result)))

现在注意do的var list中的赋值，这里的机制是平行赋值，类似与let的方式，而let*则是逐步赋值。比如fact(5),第一次初始化的时候i为5，result为1，然后测试test之后更新变量列表，i 的值变为4，但是result计算的时候还是使用前面i = 5的值，得到result = 5, 这个更新可以理解为一步完成，即里面的变量的计算得到的新值暂时不会覆盖掉变量，等到整个 var list计算完成后，直接将所有变量一次更新。

当一些变量更新式需要判断条件的时候，将其写在var list中会显得非常臃肿影响可读性，最好在body中来进行操作

do可以同时遍历多个list，如要在两个list中查找第一个相同的元素（元素的位置也相同）

(defun find-matching-ele (x y)
  (do ((x1 x (rest x1))
       (y1 y (rest y1)))
      ((or (null x1) (null y1)) nil)
    (if (equal (first x1) (first y1)) (return (first x1)))))

11.9 do*

do*类似与let*，都是逐步对var list进行求值，除此之外用法与do一样

ex 11.11

(defun find-largest (list-of-numbers)
  (do* ((list1 list-of-numbers (rest list1))
        (largest (first list-of-numbers)))
       ((null list1) largest)
    (when (> (first list1) largest) (setf largest (first list1)))))

ex 11.12

(defun power-of-2 (n)
  (do ((i n (decf i 1))
       (result 1 (+ result result)))
      ((zerop i) result)))

ex 11.13

(defun first-non-integer (x)
  (dolist (e x 'none)
    (unless (integerp e) (return e))))

ex 11.15

(defun ffo-with-do (x)
  (do ((z x (rest z))
       (e (first x) (first z)))
      ((null z) nil)
    (when (oddp e) (return e))))

这段程序要返回list中的第一个出现的奇数，但存在一个问题，当第一个奇数是x中的最后一个元素的时候，将会返回nil，因为这里用并行赋值的do，当z更新为nil，e将更新为最后一个元素，此时test已经返回nil结束函数，没有机会再进入body

11.11 implicit blocks

block是一块表达式，可以包含多个语句，可以通过return from block-name来从这个块返回，而不去执行这个块中return后面的表达式, 每个块都有一个名字，如一个函数就是一个块名

比如函数square-list接受参数list，返回里面每个元素的平方，如果遇到list中有不是数字的元素，则返回`nope

(defun square-list (x)
  (mapcar #'(lambda (e) (if numberp e) (* e e) (return-from square-list 'nope)) x))

(square-list '(1 2 3 4)) -> (1 4 9 16)
(square-list '(1 2 hello)) -> nope

函数在遇到不是数字的元素时，直接就从整个函数返回了，而不只是从lambda函数和mapcar中返回

return-from函数从最里面的block开始找要返回的块名。一般的循环函数dotimes,dolist,do,do*等都包含在一个隐式的块名nil中，前面的(return x)实际上是(return-from nil x)的简写

ex 11.18

(do ((i 0 (+ 1 i)))
    ((equal i 5) i)
    (format t "~&i = ~S" i))

ex 11.21

(defun fib (n)
  "n should > 0"
  (do ((i 2 (+ i 1))
       (cur 1 (+ cur prev))
       (prev 0 cur))
      ((> i n) cur)))

lisp toolkit: time

time macro function可以获取计算一个表达式所用的时间，内存，和其他一些有用信息

> (time (+ 1 1))
real time: ... sec.
run time: ... sec.
space: ... bytes

11.13 optional args

函数中加入&optional可以使用缺省参数，默认为nil

(defun foo (x &optional y)
  (format t "~&x is ~S" x)
  (format t "~&y is ~S" y)
  (list x y))

> (foo 3 5)
x is 3
y is 5
(3 5)

> (foo 3)
x is 3
y is nil
(3 nil)

可以自己设定缺省值，如&optional (name value)

11.14 rest args

&rest后面跟的参数会以一个list的形式传递，因此可以用来传递任意数量的参数

(defun average (&rest args)
  (/ (reduce #'+ args) (length args) 1.0))

使用递归的时候要非常注意&rest的使用，因为第一次调用的时候将参数打包成一个list,这样第二次调用的时候，会再将这个list作为第一个元素放到一个list中，变成双重的list。要解决这个问题可以使用apply，递归调用的时候仍然只是一个list的形式，如下面函数求一个list的元素的平方数

(defun square-all (&rest args)
  (if (null args) nil 
    (cons (* (first args) (first args)) (apply #'square-all (cdr args)))))

11.15 keyword args

前面使用过的关键字参数如member中设置比较用的函数，(member x y :test #'equal)

使用&key可以自己定义函数的关键字参数，&key后面可以跟任意的关键字参数，使用默认值的方式和&optional 相同，形如(key value). 注意调用时关键字参数前面有冒号:

11.16 &aux vars

&aux可以用来定义辅助的局部变量，使用方法：&aux (name [var-expression])，定义一个名为name的局部变量，通过计算var-expression的值得到初始化的值，如果只写name则默认初始化为nil

如求平均值函数中使用辅助变量保存list的长度

(defun average (&rest args &aux (len (length args))) (/ (reduce #'+ args) len 1.0))

&aux的功能都可以使用let*来实现，都是创建新的局部变量，而且时逐个赋值