scheme - 在 Racket 中使用 peano 数进行划分

Question

我正在尝试在 Racket 中使用 peano numbers 集成一个算术函数。我只使用递归(没有 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))))))

很长一段时间以来，我一直在努力解决这个问题，但一直没有成功。基本上，在除法函数中，我试图编写所有基本情况以结束递归，否则进行递归。

我也在网上搜索了一下，似乎没有什么适合我想做的...

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

Answer 1

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

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

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

> (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 是“递减的”，但当它变为零时(在基本情况下)从未对其进行测试。为避免这种情况，请参阅下面讨论的版本。

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

因此，sub 的先前定义也非常低效，因为对于递归的每一步，都会访问列表。下面是一个更有效(和正确!)的定义，其中避免了相等性测试并正确处理了递归:

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

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