Racket递归合同

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叶val) )之后，它不应该停止吗？即使它检查了第二个谓词，(叶'a)显然不是一个节点，那么它为什么要递归地再次调用树呢？

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