1

我正在学习如何在方案中使用高阶函数。我得到了使用高阶函数的想法，但是我在使用它们时遇到了麻烦。对于这个学习练习，我宁愿只使用过滤器、折叠和/或映射的某种组合。

例如，我想构造两个列表之间的集合差异，分别称为 A 和 B。我将集合差异定义为 x，这样 x 是 A 的元素，但 x 不是 B 的元素。我只想使用函数映射、过滤和折叠。例如：

令 A = (1 8 6 2)

令 B = (5 7 9 1 6)

A 和 B 的集合差为 (8 2)

这个想法是通过遍历 A 的元素并查看 A 的元素是否等于 B 的元素来构造一个新列表，如果是，则不要将 a 添加到新列表中；否则将 a 添加到新列表中。

我的算法思路是这样的：

让 neq 为“不等于”

  1. 对于 A 中的每个 a 和 B 中的 b 计算表达式：(neq? a b)

    对于 a = 1，我们有：

    (和 (neq?1 5) (neq?1 7) (neq?1 9) (neq?1 1) (neq?1 6))

  2. 如果此表达式为真，则 a 进入新列表；否则不要将 a 添加到新列表中。在我们的示例(neq? 1 1)中，计算结果为 false，因此我们不会将 1 添加到新列表中。

我的整个过程几乎都依赖于 1，这就是我遇到麻烦的地方。

  1. 我该如何做第 1 步？
  2. 我看到在第 1 步中我需要一些map和fold函数的组合，但是如何获得and a neq b分布式？

编辑这是我拥有的最接近的样本：

(fold-right (trace-lambda buggy (a b c) (and (neq? a b))) #t A B)
|(buggy 3 5 #t)
|#t
|(buggy 2 4 #t)
|#t
|(buggy 1 1 #t)
|#f
#f

上面显示了我的匿名函数试图执行 (and (neq?ab)) 链的痕迹。但是，它只对 A 和 B 中相同位置/索引的元素执行此操作。

非常感谢所有帮助！

4

4 回答 4

3

的简化版本使用member很容易实现fold，当然：

(define (member x lst)
  (fold (lambda (e r)
          (or r (equal? e x)))
        #f lst))

现在，有了这个，剩下的就很简单了：

(define (difference a b)
  (filter (lambda (x)
            (not (member x b)))
          a))

如果您想将所有这些合并到一个功能中（使用您的neq?），您可以执行以下操作：

(define (difference a b)
  (filter (lambda (x)
            (fold (lambda (e r)
                    (and r (neq? e x)))
                  #t b))
          a))
于 2013-02-03T15:35:51.443 回答
3

在 Haskell 中，fold由于惰性求值，它能够短路求值。

但是在Scheme中这是不可能的。这就是为什么在 Racket 中，例如，为此提供了一个特殊功能ormap，它能够进行短路评估。IOW 它是一种特殊的类型fold，必须在 Scheme 中显式地单独定义，因为 Scheme 不是惰性的。因此，根据您的情况，我认为可以将其用作特殊的fold.

使用它，我们得到

(define (diff xs ys) 
  (filter 
    (lambda (y) 
      (not (ormap (lambda (x) (equal? x y))     ; Racket's "ormap"
                  xs))) 
    ys))

如果您的元素可以排序，最好将集合维护为有序（升序）列表；然后diff可以更有效地实现，比较两个列表中的头元素并相应地推进，以线性时间工作。

于 2013-02-04T18:31:02.380 回答
1

使用球拍：

(define A '(1 8 6 2))

(define B '(5 7 9 1 6))

(filter-not (lambda (x) (member x B)) A)

 ==> '(8 2)
于 2013-02-03T03:09:54.193 回答
1

当然，在 Scheme 中可以在第一场比赛的短路之上实现member：fold

(define (member x lst)
  (call-with-current-continuation
    (lambda (return)
      (fold (lambda (e r)
              (if (equal? e x)
                  (return #t)
                  r))
            #f lst))))
于 2016-06-11T10:25:26.367 回答