recursion - scheme::contract violation: 递归过程

Question

我需要编写一个以列表作为参数的方案程序，该列表定义了奖励分数、玩家 A 得分和玩家 B 得分。该函数应根据分数确定谁是赢家:

例如，这是我在下面使用的分数列表:

(define scores '(
                 (5 . (5 . 3)) ; points awarded = (car (car scores)) 5; player A score = cadr (car scores)) 5; player B score (cddr (car scores)) 3;
                 (5 . (6 . 2))
                 (5 . (8 . 4))
                 (5 . (5 . 1))))

所以为了澄清，分解列表中的第一个列表:

5 = 奖励积分 (car (car scores)) ;

A = Player A Score (cadr (car scores)) ;(第一个元素为 5，第二个元素为 6，依此类推)

B = Player B Score (cddr (car scores)) ;(第一个元素为 3，第二个元素为 2，依此类推)

问题是我创建了一个递归函数，它在递归的第一次迭代中爆炸。但我不明白为什么？

#lang scheme

(define (game-winner scores)  
  (define A 0)
  (define B 0)
  (cond
    ((empty? scores) '()))
  (if ( > (cadr (car scores)) (cddr (car scores)) )
      (+ A (car (car scores)))
      (+ B (car (car scores))))
  (game-winner (cdr scores)))

输出:

car: contract violation
  expected: pair?
  given: ()

让我感到困惑的部分是，当我模拟运行递归的第一次迭代并获取函数应该的值时，我得到了正确的值:

;first loop through function

    (car (car scores))  ; 5
    (cadr (car scores)) ; 5
    (cddr (car scores)) ; 3

;second loop (1st recursive call)

    (cadr (car (cdr scores))) ; 6
    (cddr (car (cdr scores))) ; 2

如果我不明白为什么它会爆炸？它应该以与递归之前的第一次调用相同的方式工作。但我显然错过了一些东西。有什么想法吗？

附言如果我只是返回 A 或 B 而不是递归调用，我得到 0:

(define (game-winner scores)  
  (define A 0)
  (define B 0)
  (cond
    ((empty? scores) '()))
  (if ( > (cadr (car scores)) (cddr (car scores)) )
      (+ A (car (car scores)))
      (+ B (car (car scores))))
  A)

输出:0

为什么第一次调用后 A 的值(应该是 5)在我输出 A 时没有显示？ A 是否仅在 if 循环的范围内？如果是这样，我如何让它存在于该范围之外？

根据@Sylwester 的反馈，我将程序修改为:

#lang scheme

(define (game-winner scores)  
  (define A 0)
  (define B 0)
  (cond
    ((empty? scores) '())
    (( > (cadr (car scores)) (cddr (car scores)))    
     (cons (+ A (car (car scores))) (game-winner (cdr scores))))
    (cons (+ B (car (car scores))) (game-winner (cdr scores)))))

输出:

(5 5 5 5)

所以我觉得我越来越近了。但是我需要能够将 A 或 B 的所有这些加在一起并输出获胜者(A 或 B)。我如何在此基础上构建才能使其发挥作用？

Answer 1

您的代码有很多死代码，无论结果如何，它们都不会被使用，最后一个表达式将执行 (cdr scores)，无论它是否为空。

(define (game-winner scores)  
  ;; Two constants that never change from 0
  (define A 0)
  (define B 0)

  ;; Dead code. Werther it's '() or #<undefined>
  (cond
    ((empty? scores) '()))

  ;; Dead code. Becomes (+ 0 (car scores)) but never used
  (if ( > (cadr (car scores)) (cddr (car scores)) )
      (+ A (car (car scores)))  ; + never mutates A
      (+ B (car (car scores)))) ; + never mutates B

  ;; Infinite recursion. Happens no matter what is the outcome of the dead code
  (game-winner (cdr scores)))

因此，当您编写 cond 或 if 时，它应该处理所有发生的事情，以便它成为最后一个表达式:

(define (game-winner scores)
  ; local defines
  (define some-var some-expression)
  ...

  ; one expression, the result of this is the result of the procedure.
  (if (empty? scores)
      '()
      (if ....)))

编辑

这是一个递归示例，使用参数来累积分数并最终确定谁的分数最高:

(define (game-winner scores)
  (let loop ((scores scores) (a 0) (b 0))
    (if (empty? scores)
        (cond ((> a b) 'A)
              ((< a b) 'B)
              (else 'TIE)))
        (loop (cdr scores)
              (+ a (cadar scores))
              (+ b (cddar scores))))))

(game-winner scores)
; ==> A