修改元組SML

Question

計數一棵樹後，我有一個問題，我的工作，在那裏我有一次遍歷樹並計算每個節點有多少個子。

這有兩個部分，數據類型和函數本身。

---

數據類型

數據類型需要的內部節點存儲任何類型的值，並且有1-3個孩子的任何地方。葉子本身可以存儲實數或字符串列表。

​​

---

功能

接着，我必須定義一個函數，它接受一個樹，並返回一個元組（N1，N2，N3），其中n1是具有節點的數一個孩子，n2有兩個孩子的節點的數量，n3有三個孩子的節點的數量。

fun myChildren (t:'a tree) = childHelper (t, (0,0,0)); 


fun childHelper (t: 'a tree, (n1, n2, n3):int*int*int) = 
    case t of 
    Empty => 0 
    | Node (x) => childrenHelper(t, (n1 + 1, n2, n3)) 
    | Node (x, y) => childrenHelper(t, (n1 + 1, n2 + 1, n3)) 
    | Node (x, y, z) => childrenHelper(t, (n1 + 1, n2 + 1, n3 + 1)); 

---

我剛開始使用的數據類型和情況，所以它混淆了我。我想知道，我的數據類型是表示樹的最佳方式嗎？我怎麼讓我的函數遞歸地通過樹？就目前而言，它只是計算樹的第一個節點，而不是所有的節點。我也將它視爲一片葉子，因爲那時我不需要做任何事情。

我知道，在列表中，你可以做高清:: TL，是有辦法，我可以做到這一點在樹上，這樣，已經通過節點走了，我呼籲每個節點上的功能？

例如，對於Node (x, y, z)，它應該在每個節點上調用childrenHelper，但同時維護元組上的數字。任何想法如何與此一起前進？

Answer 1

首先，你不能有被命名相同的多個構造數據類型。一個將不可避免地影響另一個。是你運行該代碼，你會得到一個警告類似於：

! datatype tree = Empty 
!    | Leaf of leaf 
!    | Node of leaf * 'a tree 
!    | Node of leaf * 'a tree * 'a tree 
!    | Node of leaf * 'a tree * 'a tree * 'a tree 
! Unguarded type variables at the top-level 

這是因爲定義使用未聲明爲樹類型的一部分類型參數'a。這個改變成datatype 'a tree = ...，而不是你得到這個錯誤：

!     | Node of leaf * 'a tree * 'a tree 
!     ^^^^ 
! Illegal constructor specification: the constructor cannot be specified twice for the same datatype 

你可以做什麼，而不是是有三種不同的構造，例如

datatype 'a tree = Empty 
       | Node0 of leaf 
       | Node1 of leaf * 'a tree 
       | Node2 of leaf * 'a tree * 'a tree 
       | Node3 of leaf * 'a tree * 'a tree * 'a tree 

Are my datatypes the best way to represent the tree?

是的，你的數據類型是非常精細的。

How do I make my function recursively go through the tree?

你可以用不同的方式瀏覽一棵樹。見tree traversal和folding a tree。

in a list, you can do hd::tl , is there a way I can do that on the tree so that, having gone through the node, I call the function on each node?

您可以創建一個paramorphic功能一樣摺疊，但在參數化功能需要整個節點而不僅僅是元素的節點作爲參數：

fun para f e t = 
    let val e1 = f (e, t) 
    in case t of 
      Empty     => e1 
      | Node0 x    => e1 
      | Node1 (x, t1)   => para f e1 t1 
      | Node2 (x, t1, t2)  => para f (para f e1 t1) t2 
      | Node3 (x, t1, t2, t3) => para f (para f (para f e1 t1) t2) t3 
    end 

計數節點的數量與1，2和3的子樹是這樣的功能的特化：

fun nodecount t = 
    let fun helper ((one, two, three), t) = 
      case t of 
       Empty => e1 
       | Node0 _ => (one, two, three) 
       | Node1 _ => (one+1, two, three) 
       | Node2 _ => (one, two+1, three) 
       | Node3 _ => (one, two, three+1) 
    in para helper (0,0,0) t end 

---

編輯：是的，數據類型上面，其實是多餘的，因爲可以精確到一個葉一樹x可以寫成：

val one_leaf = Node0 (x) 
val one_leaf = Node1 (x, Empty) 
val one_leaf = Node2 (x, Empty, Empty) 
val one_leaf = Node3 (x, Empty, Empty, Empty) 

如果刪除Empty，這種冗餘會消失，但你可以不再代表空樹。一個簡單的方法來克服，這是通過使用兩種類型：

datatype 'a tree = Empty | NonEmpty of 'a tree_aux 
and 'a tree_aux = Node0 of leaf 
       | Node1 of leaf * 'a tree_aux 
       | Node2 of leaf * 'a tree_aux * 'a tree_aux 
       | Node3 of leaf * 'a tree_aux * 'a tree_aux * 'a tree_aux 

或者如果你喜歡較少的構造函數和一個預先存在的人組成類型：

datatype leaf = Slist of string list | Real of real; 
datatype 'a tree = Empty | NonEmpty of 'a tree_aux 
and 'a tree_aux = Node of leaf * ('a tree_aux * ('a tree_aux * 'a tree_aux option) option) option 

但這是稍微麻煩。