等同数字的相同类型？

Question

我有四种不同的节点类型。

leaf(Int) 
node1(Leaf, Node1) 
node2(Leaf, Node1, Node2) 
node3(Leaf, Node1, Node2, Node3) 

我希望写一个函数，主要使用模式匹配，检查如果我们有一棵树n节点的数量。例如，如果f Tree具有one leaf，two single nodes,one double nodes和three triple nodes，我运行函数计数器（Tree，c（1，2，1，3））将返回true。

---

我试图用两种不同的方式解决问题，但他们都没有工作。

第一种方法是使用帮助函数，其中帮助函数将通过Tree并计数每种节点的数量。然后简单地运行它is。

第二种方法是从元组中倒数，我们一进入就检查。我们从c(N1, N2, N3, N4)到c(N1, N2 - 1, N3, N4)，如果我们碰到一个孩子的节点。

---

与第一种方法的问题是，我试图避免使用统一功能=，所以任何想法如何，我可以去下下树，同时更新的辅助函数的元组。

第二个问题是，我无法知道它何时结束，因为它可能会到达一片叶子，但我无法到达树的另一侧继续传播元组更改。

我想最好的方式来解决这是第一个。使用助手函数，然后尝试自己查找树中节点的数量。我相信还有其他方法可以解决这个问题，但这似乎是最有效的。

---

这里是我的第一个方法的代码如下所示：

countNodes(leaf(_), c(N1, N2, N3, N4)) :- 
    c(N0 + 1, N1, N2, N3). 
countNodes(node1(_, Node), c(N1, N2, N3, N4)) :- 
    countNodes(Node, c(N1, N2 + 1, N3, N4)). 
countNodes(node2(_, Node1, Node2), c(N1, N2, N3, N4)) :- 
    countNodes(Node1, c(N1, N2, N3 + 1, N4)), 
    countNodes(Node2, c(N1, N2, N3 + 1, N4)). 

而在这一点上它基本上分崩离析。我试图添加计数节点两次，这意味着我们走得越远，它会越糟糕。关于如何重写它并避免在节点有两个或三个孩子时重复计算的想法？

谢谢，任何帮助表示赞赏:)

Answer 1

从您的代码开始，我提出以下（注意：未测试）

countNodes(leaf(_), c(1, 0, 0, 0)). 

countNodes(node1(_, Node), c(N1, N2, N3, N4)) :- 
    countNodes(Node, c(N1, N2a, N3, N4)), 
    N2 is N2a+1. 

countNodes(node2(_, Node1, Node2), c(N1, N2, N3, N4)) :- 
    countNodes(Node1, c(N1a, N2a, N3a, N4a)), 
    countNodes(Node2, c(N1b, N2b, N3b, N4b)), 
    N1 is N1a+N1b, 
    N2 is N2a+N2b, 
    N3 is N3a+N3b+1, 
    N4 is N4a+N4b. 

countNodes(node3(_, Node1, Node2, Node3), c(N1, N2, N3, N4)) :- 
    countNodes(Node1, c(N1a, N2a, N3a, N4a)), 
    countNodes(Node2, c(N1b, N2b, N3b, N4b)), 
    countNodes(Node3, c(N1c, N2c, N3c, N4c)), 
    N1 is N1a+N1b+N1c, 
    N2 is N2a+N2b+N2c, 
    N3 is N3a+N3b+N3c, 
    N4 is N4a+N4b+N4c+1. 

正如你所看到的情况leaf很简单：您只需设置值1,0,0,0和0.

对于其他情况，您必须通过子节点递归调用countNodes。接下来，您可以添加找到的值（使用is）并为本地节点添加+1。