在方案中的列表上定义“减少”

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如果至少有一个参数为真则返回真，因此#f在没有参数时返回。 and如果至少有一个参数为假，则返回假，因此#t在没有参数的情况下调用时返回。

处理交换性

加法和乘法是可交换的和结合的，因此您可以毫无问题地向要减少的序列的任一端添加单位元素。例如，无论如何插入括号，0+a+b+c 都将与 a+b+c+0 相同。但是，减法和除法没有这个特性。一般来说，abc 与 cba 不同，0-ab 与 ab-0 不同。

这意味着您的reduce 函数需要说明元素将以何种顺序组合，以及应在何处注入标识元素（或初始元素）。这通常是典型的折叠，而不仅仅是reduce。

使用初始值实现 reduce

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

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

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

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

这意味着你可以做

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

对于布尔情况，您需要像andand这样的函数or，但这些很简单：

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

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

然后你可以做

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

请注意，在除法和减法的情况下，右结合归约会将单位元素放在您想要的位置，因为您最终会'(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))))))))