在Racket中使用peano数字进行划分

Question

我试图在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))))))

我一直试图在这方面工作很长一段时间,但没有运气.基本上,在除法函数中,我试图编写所有基本情况以结束递归,否则执行递归.

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

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

Answer 1

定义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是"递减的",但是当它变为等于零时,它从未被测试(在基本情况下).要避免这种情况,请参阅下面讨论的版本.

另一个重点是equal?,由于其定义,在列表的情况下执行两个列表的访问,在找到第一个列表结束时终止,这使得它成为昂贵的操作符.

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

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

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