修改元组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 

但这是稍微麻烦。