作者在 cpdt 书的练习中指的是什么数据类型？

Question

我正在阅读 cpdt book (great thanks to the author!). Author gives (unofficial) exercises。下面有练习6：

使用自反归纳定义，定义一个 nat_tree 无限树的类型，其中叶子上的自然数和可数无限的新树从每个内部节点。定义一个函数 increment 在每个 nat_tree 的叶子。在自然 i 和树 nt 上定义函数 leapfrog。蛙跳应该递归到 i 的第 child of nt, i+1st child 该节点的 i+2nd child 下一个节点，依此类推，直到到达叶子，在这种情况下 leapfrog 应该 return 那片叶子上的数字。证明对 leapfrog 的任何调用的结果都增加了一个是在树上调用增量。

问题是：作者指的是什么数据类型？我能够创建的是

Inductive nat_tree : Set := 
| Leaf (n : nat) : nat_tree
| Node (nat -> nat_tree) : nat_tree.

与我在互联网上找到的定义完全相同。但这在我看来并不像上面的代码那样符合作者的要求。因为作者说 function increment that increments the number in every leaf of a nat_tree。但是根据这个定义，任何 nat_tree 中只有一片叶子。所以，这只是一个列表，而不是一棵树。可以在 'Node' 构造函数中再添加一个参数，例如 Node (nat->nat_tree) (nat-> nat_tree) : nat_tree，但在我看来，这个定义似乎每个内部节点恰好有 2 children，但作者说 [=13] =].

所以，我想寻求有关 nat_tree 定义的帮助。或者为了澄清为什么上面的定义对任务有好处。或任何人都能够提供的任何其他说明。

注意。我认为我们没有违反任何荣誉准则给出答案。作者从书中删除了这些练习，他说他不再支持这些练习了。作者没有要求书中的任何地方隐藏解决方案（与软件基础书相反）。此外，我能够在互联网上轻松找到该任务的几种解决方案（但它们都与上面给出的一样）。所以，我觉得这道题应该完全没问题。

Answer 1

根据练习描述，这看起来像是合适的数据类型。您可以构建具有任意数量的不同叶子的树，例如 Node (fun n => if n =? 0 then Leaf 3 else Leaf 5)、Node (fun n => Leaf n) 或 Node (fun n => Node (fun m => Leaf (n + m)).

作者在 cpdt 书的练习中指的是什么数据类型？

What the data type does author mean in exercises for cpdt book?

coq