在Lisp中实现循环的非`循环`,非变异方式？

Question

我用以下方法编写了以下循环local-time:

(defun count-dates (stop-date k)
  (loop for step = (local-time:today)
        then (local-time:timestamp- step 1 :day)
        while (local-time:timestamp>= step stop-date)
        collect (funcall k step)))

它可以像这样运行:

(count-dates (local-time:encode-timestamp 0 0 0 0 1 1 2019) #'princ)

虽然这很简单直接,但我想知道如何在没有全能loop结构的情况下编写它,并提出:

(defun count-dates2 (stop-date k)
  (reverse (labels ((f (acc step)
                      (if (local-time:timestamp>= step stop-date)
                          (f (cons (funcall k step) acc)
                             (local-time:timestamp- step 1 :day))
                          acc)))
             (f '() (local-time:today)))))

这似乎过于复杂,有reverse一个累加器.是否有更简单的方法来实现与循环相同的效果而不诉诸突变并且可能没有溢出堆栈？

Answer 1

不在Common Lisp中,不是:如果你想要一个迭代构造,你需要使用一个显式迭代构造:CL没有承诺语法递归构造实际上是迭代的. loop然而,它不是唯一的迭代构造,您当然可以编写自己的迭代和结果集合构造.

确实没有承诺你的第二个版本不会在CL中溢出堆栈:大多数当前的实现都会将尾调用编译为迭代,尽管可能无法在解释代码中处理它,但有些受到目标(例如JVM)的限制而不能做这个.还有一些主要的历史本机代码实现(例如,Symbolics CL).

有一些Lisp系列语言在语言中指定尾部调用是迭代,特别是Scheme,在这种语言中你的第二个版本没问题.

关于需要向后构建列表然后反转它们的问题:我认为这是列表在Lisp中工作方式的必然结果:如果你不满意,你只能通过添加内容来构建列表改变现有列表或采取批量复制的每一步.

当然,你可以隐藏你在幕后构建的列表的变异,这样你就不需要知道发生了什么,但这并不意味着它不是要改变结构,要么反向构建它然后反转.所以,例如,我有一个看起来像这样的结构:

(collecting
  ...
  (collect ...)
  ...)

它构建了前向列表,但它通过保留尾部指针并改变它正在构建的列表来实现这一点.

Answer 2

您也可以使用SERIES包:

(defpackage :so (:use :cl :series :local-time))
(in-package :so)

(let ((stop-date (timestamp- (today) 10 :day)))
  (scan-fn  ;; type of elements (could be T here)
            'timestamp
            ;; init function
            (lambda () (today))
            ;; step function
            (lambda (ts) (timestamp- ts 1 :day))
            ;; termination test
            (lambda (ts) (not (timestamp>= ts stop-date)))))

上面返回一个系列对象的实例,它是一个有效编译的惰性(按需)值流.在REPL中,它显示为#Z(...)(其中点是元素).如果要将其转换为列表,可以调用collect:

(collect *) ;; assuming * is the last returned value

如果你想要一个向量:

(collect 'vector **)

这使:

#(@2019-02-19T01:00:00.000000+01:00 @2019-02-18T01:00:00.000000+01:00
  @2019-02-17T01:00:00.000000+01:00 @2019-02-16T01:00:00.000000+01:00
  @2019-02-15T01:00:00.000000+01:00 @2019-02-14T01:00:00.000000+01:00
  @2019-02-13T01:00:00.000000+01:00 @2019-02-12T01:00:00.000000+01:00
  @2019-02-11T01:00:00.000000+01:00 @2019-02-10T01:00:00.000000+01:00
  @2019-02-09T01:00:00.000000+01:00)

还要注意,在collect词法包含scan-fn函数的情况下,它可以直接将代码表示为循环.例如:

(let ((stop-date (timestamp- (today) 10 :day)))
  (collect
      (scan-fn  ;; type of elements (could be T here)
       'timestamp
       ;; init function
       (lambda () (today))
       ;; step function
       (lambda (ts) (timestamp- ts 1 :day))
       ;; termination test
       (lambda (ts) (not (timestamp>= ts stop-date))))))

该collect形式macroexpanded为:

(LET* (#:STATE-1062 #:ITEMS-1063 (#:LASTCONS-1060 (LIST NIL)) #:LST-1061)
  (DECLARE (TYPE CONS #:LASTCONS-1060)
           (TYPE LIST #:LST-1061))
  (LOCALLY
   (DECLARE (TYPE TIMESTAMP #:STATE-1062)
            (TYPE TIMESTAMP #:ITEMS-1063))
   (SETQ #:STATE-1062 ((LAMBDA () (TODAY))))
   (SETQ #:LST-1061 #:LASTCONS-1060)
   (TAGBODY
    #:LL-1064
     (IF ((LAMBDA (TS) (NOT (TIMESTAMP>= TS STOP-DATE))) #:STATE-1062)
         (GO SERIES::END))
     (SETQ #:ITEMS-1063 #:STATE-1062)
     (SETQ #:STATE-1062 ((LAMBDA (TS) (TIMESTAMP- TS 1 :DAY)) #:STATE-1062))
     (SETQ #:LASTCONS-1060
             (SETF (CDR #:LASTCONS-1060) (CONS #:ITEMS-1063 NIL)))
     (GO #:LL-1064)
    SERIES::END)
   (CDR #:LST-1061)))

如Evhince所述,Common Lisp cookbook有一个关于Series的部分,请参阅https://lispcookbook.github.io/cl-cookbook/iteration.html

Answer 3

您可以通过reverse调用内部来消除一个级别的缩进.另请注意,名称count-dates不是那么好,因为一个不计算日期,而是从今天的downto映射一天的步骤stop-date.

(defun count-dates2 (stop-date k)
  (labels ((f (acc step)
             (if (local-time:timestamp>= step stop-date)
                 (f (cons (funcall k step) acc)
                    (local-time:timestamp- step 1 :day))
                 (reverse acc))))
    (f '() (local-time:today)))))

另一个迭代构造是旧的DO:

(defun count-dates (stop-date k &aux result)
  (do ((step
        (local-time:today)
        (local-time:timestamp- step 1 :day)))

      ((not (local-time:timestamp>= step stop-date))
       (reverse result))

    (push (funcall k step) result)))

但那并不比LOOP.

ITERATE是一个迭代构造,它不是标准的,但是在功能上LOOP和美学上稍微好一点.