我正在通读Seibel的"实用通用语言";并找到了这个示例宏:
(defmacro check (&rest forms)
`(progn
,@(loop for f in forms collect `(do-stuff ,f ',f))
(defun test ()
(check ( (= (+ 1 2 ) 3) (= (+ 1 2 ) 4 )))
)
do-stuff然后简单地以某种方式格式化两个参数,允许"测试"表单的真值,但这对我的问题并不重要。
我感兴趣的是将循环转换为DO,不幸的是,我完全缺乏这样做的必要技能:
(defmacro check (&rest forms)
`(progn
,@(do ((index 0 (list-length forms))
(accumulator nil))
((= index (list-length forms)) accumulator)
(push `(do-stuff ,(nth index forms) ',(nth index forms)) accumulator)
))
完成任务,我也可以这样做(将每个表单放入do中的变量中):
(defmacro check (&rest forms)
`(progn
,@(do* ((index 0 (list-length forms))
(accumulator nil)
(f (nth index forms) (nth index forms)))
((= index (list-length forms)) accumulator)
(push `(do-stuff ,f ',f) accumulator)
))
我的问题如下:
是否有更有效的方式来写这个do循环?这是实现它的好方法吗?
LOOP版本中的一些东西让我想知道是否有一种简单的方法可以在不需要定义索引变量的情况下从列表中提取元素,或者在不需要定义累加器列表的情况下重新组合已收集的元素…
如果你使用do
,你就不应该使用nth
。只遍历列表,而不是索引。
(do ((l forms (cdr l))
(accumulator nil))
((null l) (nreverse accumulator))
(let ((f (car l)))
(push `(do-stuff ,f ',f) accumulator)))
您也可以使用内置的dolist
:
(let ((accumulator nil))
(dolist (f forms (nreverse accumulator))
(push `(do-stuff ,f ',f) accumulator)))
最后是mapcar
:
(mapcar (lambda (f) `(do-stuff ,f ',f)) forms)
是否有更有效的方法来编写这个do循环?这是实现它的好方法吗?
你的代码复杂度是列表大小N的二次,因为你调用nth
来访问其中的元素,导致O(N*N)的执行时间。有一种更有效的方法来做到这一点(原始LOOP版本是线性算法的一个例子)。
这里是一个不同的版本,在遍历过程中,条目在列表的末尾排队,而不是在push
之后调用nreverse
。我添加了注释来解释每个部分的作用。
顺便说一下,我并不是说这比使用nreverse
更有效,我认为没有测试我们无法知道。然而,请注意,在这两种情况下都有很多操作(创建一个新项目,并最终改变cdr
插槽),它们只是在两次或一次传递中完成。
实际上,下面的代码离MAPCAR
的实现很近,只有一个列表可以遍历(而不是标准中的可变版本)。
(defun expand-check (form)
`(do-stuff ,form ',form))
回想一下,您可以仅(mapcar #'expand-check checks)
来获得所需的结果。
无论如何,这是一个DO版本:
(defun expand-checks (checks)
;; LIST-HOLDER is just a temporary cons-cell that allows us to treat
;; the rest of the queue operations without having to worry about
;; the corner case of the first item (the invariant is that LAST is
;; always a cons-cell, never NIL). Here LIST-HOLDER is initially
;; (:HANDLE), the first value being discarded later.
(let ((list-holder (list :handle)))
;; DO is sufficient because the iterator values are independant
;; from each other (no need to use DO*).
(do (;; descend the input list
(list checks (cdr list))
;; update LAST so that it is always the last cons cell, this
;; is how we can QUEUE items at the end of the list without
;; traversing it. This queue implementation was first
;; described by Peter Norvig as far as I known.
(last list-holder (cdr last)))
;; End iteration when LIST is empty
((null list)
;; In which case, return the rest of the LIST-HOLDER, which
;; is the start of the list that was built.
(rest list-holder))
;; BODY of the DO, create a new cons-cell at the end of the
;; queue by mutating the LAST const cell.
(setf (cdr last)
(list (expand-check
(first list)))))))
首先,任何形式的
(loop for v in <list> collect (f v ...))
可以很容易地表示为mapcar
:
(mapcar (lambda (v)
(f v ...))
<list>)
有趣的情况是当loop
有时只收集一个值,或者当迭代处理一些更复杂的事情时。
在这种情况下,一个很好的方法是将迭代位和"收集值"位分离出来,使用do
或其他一些机制来执行迭代和其他一些机制来收集值。
收集就是其中之一。因此,例如,您可以使用dolist
来遍历列表,使用collecting
来收集值。也许我们只想收集非nil
值或其他让它更有趣的东西:
(collecting
(dolist (v <list>)
(when v
(collect (f v ...)))))
所有这些都比简单的loop
情况更冗长,但是例如collecting
可以做一些用loop
来表达很痛苦的事情。