等同數字的相同類型？

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。