为什么方案"过滤"表单不能"按顺序"处理列表元素？

Question

(filter procedure list)procedure应用于list的每个元素，并返回一个新列表，仅包含procedure返回 true.
(R. Kent DybvigThe Scheme Programming Language) (在线)

从这个描述中可能看不出的是，虽然返回的元素 列表的出现顺序与list中的顺序相同，procedure的调用顺序不是 在 R6RS 中指定。(但是，Racket将程序"从头到尾应用于每个元素")

最近活跃的答案 提到它需要一个filterfunc，该适用于其参数列表按顺序。应该如何编写此函数？

提供了我对问题的解释的答案。

Answer 1

Scheme 实现可能使用什么顺序，为什么？让我们试试看(所有代码都在Chez Scheme REPL中运行)：

1. 应用程序的显示顺序

> (filter (lambda (x) (display x) (even? x))
'(0 1 2 3 4 5)))
452301(0 2 4)
> 

2. 为什么这个顺序？
   R6RS 实现必须检查list是否是正确的列表

• 以空列表结尾：

> (filter (lambda (x) (display x) (even? x))
'(0 1 2 . 3)))
Exception in filter: (0 1 2 . 3) is not a proper list
> 

• 无循环性：

> (define xs '(0 1 2 3))
> (set-cdr! (cdddr xs) (cdr xs))
> (filter (lambda (x) (display x) (even? x)) xs)
Exception in filter: (0 1 2 3 1 2 ...) is not a proper list
> 

• 在Chez计划中实施filter，以检查这些要求 在过滤时，导致谓词应用程序的"452301"顺序， 可以在这里看到
  (第 589-617 行：下面包含一个版本作为剧透，作为滚动浏览的替代方案 GitHub上的源代码)

3. What？
   Chez Scheme代码使用"龟兔"算法 以检测周期。如果没有错误检查，代码可能是：

> (let ([filter
(lambda (pred? ls)
(let f ([fast ls])
(if (pair? fast)
(let ([rest (f (cdr fast))])
(if (pred? (car fast))
(cons (car fast) rest)
rest))
'())))])

(filter (lambda (x) (display x) (even? x))
'(0 1 2 3 4 5)))
543210(0 2 4)
> 

(标识符fast用于匹配Chez方案代码：否则可以ls)

4. 如何将其更改为"从第一个到最后一个"pred?？

• 将rest变量替换为累加器(将以下内容与上面的 3 进行比较; 更改很小，但过滤后的元素cons到 ACC， 所以必须颠倒过来才能给出结果)：

> (let ([filter
(lambda (pred? ls)
(let f ([fast ls] [acc '()])
(if (pair? fast)
(f (cdr fast)
(if (pred? (car fast))
(cons (car fast) acc)
acc))
(reverse acc))))])

(filter (lambda (x) (display x) (even? x))
'(0 1 2 3 4 5)))
012345(0 2 4)
> 

所以 4 可以用作所需的filterfunc.这将是一个有趣的练习 添加错误检查，如 Chez 方案实现，这实际上是：

<块引用类>

(define (filter pred? ls)(unless (procedure? pred?)
(error #f "not a procedure" pred?))
(or (let f ((pred? pred?) (fast ls) (slow ls))
(if (pair? fast)
(let ((fast1 (cdr fast)))
(if (pair? fast1)
(and (not (eq? fast1 slow))
(let ((fast2 (cdr fast1)))
(let ((rest (f pred? fast2 (cdr slow))))
(and rest
(if (pred? (car fast))
(if (pred? (car fast1))
(if (eq? rest fast2)
fast
(list* (car fast)
(car fast1) rest))
(cons (car fast) rest))
(if (pred? (car fast1))
(if (eq? rest fast2)
fast1
(cons (car fast1) rest))
rest))))))
(and (null? fast1)
(if (pred? (car fast))
fast
'()))))
(and (null? fast) '())))
(error #f "circular/improper list" ls)))

Answer 2

它涉及你不应该在过程中使用某些外部变量的突变，它假设实现可以应用并行性，例如map-reduce。