1

(filter procedure list)适用procedure于的每个元素list 并返回一个新列表，该列表仅包含procedure 返回 true 的元素。
（R. Kent Dybvig The Scheme 编程语言）（在线）

从这个描述中可能不明显的是，虽然返回列表中的元素以与 中相同的顺序出现，但R6RS 中没有指定list调用的顺序。procedure（然而，Racket 将程序“从第一个到最后一个”应用于每个元素）

最近一个活跃的答案 提到它需要一个filterfuncwhich 在其参数列表 中按顺序工作。应该如何编写这个函数？

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

4

2 回答 2

2

Scheme 实现可能使用什么顺序，为什么？让我们尝试一下（所有代码都在 Chez Scheme REPL 中运行）：

  1. 应用程序的显示顺序
> (filter (lambda (x) (display x) (even? x))
    '(0 1 2 3 4 5)))
452301(0 2 4)
>
  1. 为什么是这个命令？
    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 Scheme 中的实现，filter它在过滤时检查这些要求，导致谓词应用程序的“452301”顺序，可以在这里
    看到 （第 589-617 行：下面包含一个版本作为扰流板，作为滚动浏览源代码的替代方案在github上）
  1. 什么？
    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 Scheme 代码：可能是ls其他情况）

  1. 如何将其更改为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 可以用作 required filterfunc。添加像 Chez Scheme 实现这样的错误检查将是一个有趣的练习，它实际上是：

(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)))

于 2021-12-03T12:40:49.480 回答
1

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

于 2021-12-05T07:08:18.793 回答