recursion - 在方案列表中定义 "reduce"

Question

(define (BOR x y)
  (cond
    ((equal? x #t)  #t)
    ((equal? y #t)  #t)
  (else           #f))
)

(define (reduce op list)
  (cond
    ((null? list)
      (cond
        ((BOR (equal? op +) (equal? op -))  0)
        ((BOR (equal? op *) (equal? op /))  1)
        ((equal? op BOR)                    #f)
        ((equal? op BAND)                   #t)
      (else                               #f)))
  (else  (op (car list) (reduce op (cdr list)))))
)

(display (reduce + '(1 2 3 4 5)))
(newline)
(display (reduce - '(100 20 30)))
(newline)

为了可见性，我加入了“BOR”。这是我的输出:

120
110

我的定义似乎是有效的，但没有按照我的意愿评估减法和除法。我尝试删除 BOR，在检查空列表后留下 6 个条件进行检查，输出没有任何变化。

您可能会注意到行为有点像这样:

(reduce - '(100 20 30 5 40)) is called.
This returns (+ (- (+ (- 100 20) 30) 5) 40).
Which is equivalent to 100 - 20 + 30 - 5 + 40 = 145.

这种触发器行为仅在我除法或减法时发生。我所有的其他操作都执行得很好。这是我的作业，所以请不要直接回答。也许我错过了方案递归的一些关键行为模式？任何帮助将不胜感激。

Answer 1

处理零和一个参数的情况

操作 + 和 * 已经在 Scheme 中定义为接受 0 个参数并在这些情况下返回恒等函数。减法和除法函数没有这个属性，主要是因为它们有一个参数的特殊情况，因为让 (/2) 返回 1/2 更方便> 比返回 2 更方便，(- 2) 返回 -2 比 2 更方便。

形式 or 和 and 不是函数，但也被定义为可以接受任意数量(包括零)的参数。如果至少有一个参数为真，则 or 返回 true，因此在没有参数时返回 #f。 and 如果至少有一个参数为 false，则返回 false，因此在不带参数调用时返回 #t。

处理交换性

加法和乘法具有交换律和结合律，因此您可以毫无问题地将恒等元添加到要归约的序列的任一端。例如，无论如何插入括号，0+a+b+c 都将与 a+b+c+0 相同。但是，减法和除法没有这个性质。一般来说，a-b-c 与 c-b-a 不同，0-a-b 与 a-b-0 不同。

这意味着您的 reduce 函数需要说明元素的组合顺序，以及应该在何处注入(inject)标识元素(或初始元素)。这是一般折叠的典型特征，而不仅仅是 reduce。

使用初始值实现 reduce

我知道您说过您不想要解决方案，因为这是家庭作业，但我认为这段代码与您自己的代码完全不同，所以这不是什么大问题。不仅如此，Stack Overflow 的答案应该对每个人都有用，而不仅仅是最初的提问者。最后，reduce 是一个非常常见的函数，不难找到它的实现。

(define (reduce fn list init)
  (if (null? list) init
      (fn (car list)
          (reduce fn (cdr list) init))))

这是一个 right-associative 折叠，它将 init 注入(inject)到列表中最后一个元素的右边。也就是说，对于 (reduce fn '(a b c) i)，你得到

(fn a (fn b (fn c i)))

这意味着你可以做到

(reduce + '(...) 0)
(reduce - '(...) 0)
(reduce * '(...) 1)
(reduce / '(...) 1)

对于 bool 情况，您需要像 and 和 or 这样的函数，但这些很简单:

(define (%or x y)
  (or x y))

(define (%and x y)
  (and x y))

然后你可以做

(reduce %or  '(...) #t)
(reduce %and '(...) #f)

请注意，在除法和减法的情况下，右结合 reduce 将标识元素放在您想要的位置，因为您最终将 '(a b c d) 变成了

(a - (b - (c - (d - 0))))

(a / (b / (c / (d / 1))))

但是，这很可能不是您想要的，因为这意味着您会得到所描述的“触发器”行为。例如，

a/(b/c) = (ac)/b ≠ (a/b)/c

对于除法和减法，您可能需要左结合归约。这些实际上恰好在 Scheme 中更有效一些，因为它们可以尾递归地实现，因此使用更少的堆栈空间。

(define (reduce fn init list)
  (if (null? list) init
      (reduce fn (fn init (car list)) (cdr list))))

这是左关联折叠对我来说最自然的方式，因为初始值位于列表的左侧，所以我们有 ((((i • a) • b) • c)。当然，问题是对于除法和减法，我们确实希望将“初始”值放在末尾。您可以编写一个版本来做到这一点，但它有点复杂，因为您必须检查三种情况:(i) 没有元素的列表；(ii) 有一个元素的列表；以及 (iii) 至少有两个元素的列表:

(define (reduce fn list final)
  (cond
    ((null? list)
     init)
    ((null? (cdr list)) 
     (fn (car list) init))
    (else
     ;; do a normal left-associative reduce over the 
     ;; list, but add the final element at the end.
     (let red ((init (fn (car list) (cadr list)))
               (list (cddr list))
       (if (null? list) (fn init final)
           (red (fn init (car list)) (cdr list))))))))