Разделение с использованием чисел Пеано в Racket - PullRequest
Новая
       9

Разделение с использованием чисел Пеано в Racket

0 голосов
/ 29 января 2019

Я пытаюсь интегрировать арифметическую функцию с использованием чисел Пеано в Racket.Я использую только рекурсию (без циклов for / while)

Сейчас я работаю над делением.Я не уверен, что нахожусь в правильном пути, но похоже, что Ракет дает мне ошибку памяти.Вот что у меня есть: 

; 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))))))

Я пытался работать над этим довольно долго, но безуспешно.По сути, в функции деления я пытаюсь записать все базовые сценарии, чтобы завершить рекурсию, иначе делаю рекурсию.

Я также искал в интернете, и, кажется, ничто не соответствует тому, что я пытаюсь сделать ...

Любая помощь / совет помогут.Спасибо!

1 Ответ

0 голосов
/ 29 января 2019

Определения sub и div неверны.Вам следует использовать equal? вместо eq? для сравнения чисел Пеано.

Это потому, что eq? проверяет объект идентичность : когда два значения одинаковы object, тогда как 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, функция зацикливается навсегда.Это в математическом смысле правильно, так как деление на ноль является неопределенной операцией.Однако, с точки зрения программирования, я думаю, что было бы более уместно возвратить какую-то ошибку.

...