Ракетка - рекурсивные контракты

Question

Я пытался заключить рекурсивный контракт для моей структуры двоичного дерева:

(struct node (l r)) 
(struct leaf (val))

(define (tree-of val)
    (or/c (struct/c leaf val) (struct/c node (tree-of val) (tree-of val))))

(define/contract (id-tree t)
    (-> (tree-of symbol?) (tree-of symbol?))
    t)

(id-tree (leaf 'a))

Кажется, что мой контракт приводит к бесконечному циклу, не знаю почему.Прежде всего, не должно ли это остановиться после того, как или / c получит какое-либо положительное значение (в данном случае из (struct / c leaf val))?Даже если он проверяет второй предикат, (leaf 'a), очевидно, не является узлом, так почему он будет рекурсивно вызывать tree-of снова?

Answer 1

В некотором смысле, есть две фазы: вычисление контракта и проверка контракта. Ваш пример не заканчивается в фазе вычисления контракта.

Предположим, вы добавили (or/c <a> <b>) к значению x. or/c - это просто нормальная функция, поэтому при вызове по значению (что и есть у Racket) будут вычислены и <a>, и <b>.

Если ничего не происходит не так, <a> и <b> должны оценить значения контракта va и vb соответственно. Затем проверка контракта начинается с проверки x против va. Если это не удается, тогда он проверяет x против vb.

Проблема с вашим примером заключается в том, что процесс вычисления значений контракта даже не прекращается. На тот момент проверки еще не проводились.

Чтобы выполнить то, что вы хотите сделать, используйте flat-rec-contract:

(define (tree-of/c val)
  (flat-rec-contract tree-of
                     (struct/c leaf val)
                     (struct/c node tree-of tree-of)))