3

我正在尝试在 Racket 中使用 peano 数字集成算术函数。我只使用递归（没有 for / while 循环）

现在，我在做分工。我不确定我是否走在正确的道路上，但似乎 Racket 给了我一个内存错误。这是我到目前为止所拥有的：

; Basic Peano axioms

(define (zero? n)
  (eq? n 'zero))

(define (nat? x)
  (cond
    [(zero? x) #t]
    [(pair? x) (and (eq? (first x) 'succ) (nat? (second x)))]
    [else #f]))

(define (succ n)
  (list 'succ n))

(define (pred n)
  (if (zero? n) 'zero (second n)))

; comparison of Peano numbers

(define (ltnat? m n)
  (cond
    [(zero? n) #f]
    [(zero? m) #t]
    [else (ltnat? (pred m) (pred n))]))

; Subtraction

(define (sub m n)
  (if (eq? m n)
      'zero
      (succ (sub (pred m) n)))
)

; Division

(define (div m n)
  (if (zero? m)
      'zero
      (if (eq? m n)
          '(succ zero)
          (if (ltnat? m n)
              'zero
              (succ (div (sub m n) n))))))

我已经尝试了很长时间，但没有运气。基本上，在除法函数中，我试图编写所有基本案例来结束递归，否则进行递归。

我也在互联网上搜索过，似乎没有什么适合我想要做的......

任何帮助/建议都会有所帮助。谢谢！

4

1 回答 1

6

sub和的定义div不正确。您应该使用equal?而不是eq?比较 Peano 数字。

这是因为eq?测试对象身份：当两个值是同一个对象时，同时equal?测试结构相等性：例如，当两个列表具有相同顺序的相同元素时。

在这种情况下，由于您正在比较程序不同部分中使用构造函数构建的列表，即使它们在结构上相同，它们也是不同的对象：

> (eq? 'zero 'zero) ; two constant symbols are made unique,
#t                  ; representing the same value in memory
> (eq? '(succ zero) '(succ zero)) ; two lists are read as
#f                                ; two different values
> (equal? '(succ zero) '(succ zero))
#t          ; the comparison here is done element by element
> (let ((a '(succ zero))) ; here we compare the same object
    (eq? a a))  ; the list is read only once and stored in memory
#t

因此，例如，sub您可以使用以下定义来代替 的定义：

(define (sub m n)
  (if (equal? m n)
      'zero
      (succ (sub (pred m) n)))
)

但是请注意，当第二个参数大于第一个参数时，此定义陷入无限循环。事实上，在递归调用m中是“递减”的，但是当它变得等于 0 时（在基本情况下）它永远不会被测试。为避免这种情况，请参阅下面讨论的版本。

另一个重要的一点是equal?，由于它的定义，在列表的情况下执行两个列表的访问，当找到第一个列表结尾时终止，这使得它成为一个昂贵的运算符。

因此，前面的定义sub也相当低效，因为对于递归的每一步，都会访问列表。下面是一个更有效（和正确！）的定义，其中避免了相等测试并正确处理了递归：

(define (sub m n)
  (cond
    [(zero? m) 'zero]
    [(zero? n) m]
    [else (sub (pred m) (pred n))]))

最后一点：同样在 的定义中div，当除数是'zero函数时，函数将永远循环。这在数学意义上是正确的，因为除以零是一个不确定的操作。但是，从编程的角度来看，我认为返回某种错误会更合适。

于 2019-01-29T06:57:23.920 回答