在 SML 中对树进行计数后修改元组

Question

我有一个问题正在研究，我必须遍历一棵树并计算每个节点有多少 children。

这有两部分，数据类型和函数本身。

数据类型

数据类型要求内部节点存储任何类型的值，并且具有 1-3 children 之间的任何值。叶子本身存储一个实数或一个字符串列表。

datatype leaf = Slist of string list | Real of real;
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

函数

接下来，我必须定义一个函数，它接受一棵树和 returns 一个元组 (n1, n2, n3)，其中 n1 是具有一个 child, n2 的节点数有两个 children 的节点数，n3 有三个 children.

的节点数

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));

我才刚刚开始使用数据类型和案例，所以这让我感到困惑。我想知道，我的数据类型是表示树的最佳方式吗？以及如何使我的函数递归地遍历树？就目前而言，它只计算树的第一个节点而不是所有节点。我也放弃了它是一片叶子的情况，因为那时我不需要做任何事情。

我知道在列表中，您可以执行 hd::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 and 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

但这有点麻烦。

在 SML 中对树进行计数后修改元组

Modifying tuples after counting a tree in SML

tree

recursion

types

sml