在 SML 中对树进行计数后修改元组 [英] Modifying tuples after counting a tree in SML

问题描述

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

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

<小时>

数据类型

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

datatype Leaf = Slist of string list |真实的真实；数据类型树 = 空|叶子的叶子|叶节点 * '一棵树|叶节点*'一棵树*'一棵树|叶子节点*'一棵树*'一棵树*'一棵树

<小时>

功能

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

fun myChildren (t:'a tree) = childHelper (t, (0,0,0));fun childHelper (t: '一棵树, (n1, n2, n3):int*int*int) =案例 t空 =>0|节点 (x) =>childrenHelper(t, (n1 + 1, n2, n3))|节点 (x, y) =>childrenHelper(t, (n1 + 1, n2 + 1, n3))|节点 (x, y, z) =>childrenHelper(t, (n1 + 1, n2 + 1, n3 + 1));

<小时>

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

我知道在列表中，您可以执行 hd::tl，有没有办法在树上执行此操作，以便在遍历节点后，在每个节点上调用函数?

例如，对于Node(x, y, z)，它应该在每个节点上调用childrenHelper，但同时保持元组上的编号.关于如何继续进行的任何想法?

解决方案

首先，一个数据类型不能有多个同名的构造函数.一个将不可避免地覆盖另一个.如果您运行此代码，您会收到类似于以下内容的警告:

<代码>！数据类型树 = 空！|叶子的叶子！|叶节点 * '一棵树！|叶节点*'一棵树*'一棵树！|叶子节点*'一棵树*'一棵树*'一棵树！顶层不受保护的类型变量

这是因为定义使用了一个类型参数 'a，它没有被声明为树类型的一部分.将其更改为 datatype 'a tree = ...，您会收到此错误:

<代码>！|叶节点*'一棵树*'一棵树！^^^^！非法构造函数规范:不能为同一数据类型指定两次构造函数

你可以做的是使用三个不同的构造函数，例如

datatype '一棵树 = 空|叶节点0|叶节点1 * '一棵树|叶节点2 * '一棵树* '一棵树|叶子节点3 * '一棵树* '一棵树* '一棵树

<块引用>

我的数据类型是表示树的最佳方式吗?

是的，您的数据类型非常好.

<块引用>

如何让我的函数递归遍历树?

你可以用不同的方式穿过一棵树.请参阅树遍历和折叠一棵树.

<块引用>

在列表中，您可以执行hd::tl，有没有办法在树上执行此操作，以便在遍历节点后调用每个节点上的函数?

您可以创建一个类似于折叠的 paramorphic 函数，但参数化函数采用完整节点而不仅仅是节点中的元素作为参数:

有趣的 para f e t =让 val e1 = f (e, t)在 t 的情况下空 =>e1|节点0 x =>e1|节点 1 (x, t1) =>段 f e1 t1|节点 2 (x, t1, t2) =>段 f (段 f e1 t1) t2|节点 3 (x, t1, t2, t3) =>段 f (段 f (段 f e1 t1) t2) t3结尾

计算具有 1、2 和 3 个子树的节点数是该函数的特化:

有趣的节点数 t =让有趣的帮手 ((一、二、三), t) =案例 t空 =>e1|节点0 _ =>(一二三)|节点 1 _ =>(一+1、二、三)|节点 2 _ =>(一、二+1、三)|节点 3 _ =>(一、二、三+1)在 para helper (0,0,0) t 结束

<小时>

是的，上面的数据类型实际上是多余的，因为一棵树只有一个叶子 x 可以写成:

val one_leaf = Node0 (x)val one_leaf = Node1(x，空)val one_leaf = Node2(x，空，空)val one_leaf = Node3(x，空，空，空)

如果您删除 Empty，这种冗余就会消失，但您不能再表示空树.克服此问题的一种简单方法是使用两种类型:

datatype 'a tree = Empty |'a tree_aux 的非空和 'a tree_aux = 叶子的 Node0|叶节点1 * 'a tree_aux|叶子节点2 * 'a tree_aux * 'a tree_aux|叶子节点3 * 'a tree_aux * 'a tree_aux * 'a tree_aux

或者，如果您更喜欢更少的构造函数和由预先存在的构造函数组成的类型:

datatype Leaf = Slist of string list |真实的真实；数据类型 '一棵树 = 空 |'a tree_aux 的非空和 'a tree_aux = 叶节点 * ('a tree_aux * ('a tree_aux * 'a tree_aux 选项) 选项) 选项

但这有点麻烦.

I have a question I'm working on, where I have to traverse a tree once and count how many children each node has.

There are two parts to this, the datatype, and the function itself.

---

Datatype

The datatype requires that the internal nodes store a value of any type and have anywhere from 1-3 children. The leaves themselves store either a real number or a string list.

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

---

Function

Next, I have to define a function that takes a tree, and returns a tuple (n1, n2, n3), where n1 is the number of nodes having one child, n2 number of nodes with two children, n3 number of nodes with three 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));

---

I'm just starting to use datatypes and cases, so it's confusing for me. I was wondering, are my datatypes the best way to represent the tree? And how do I make my function recursively go through the tree? As it stands, it just counts the first node of the tree instead of all of it. I'm also leaving off the case that it's a leaf, since at that point I don't need to do anything.

I know that 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?

For example, for Node (x, y, z), it should call childrenHelper on each node, but at the same time, maintain the number on the tuples. Any ideas on how to go forward with this?

解决方案

First off, you cannot have a datatype with multiple constructors that are named the same. One will inevitably shadow over the other. Were you to run this code, you'd get a warning similar to:

! 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

This is because the definition uses a type parameter 'a that isn't declared as part of the tree type. Changing this into datatype 'a tree = ..., you instead get this error:

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

What you can do instead is have three different constructors, e.g.

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?

Yes, your datatype is very fine.

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

You can go through a tree in different ways. See 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?

You could create a paramorphic function alike a fold, but where the parameterised function takes the full node and not just the element in the node as argument:

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

Counting the number of nodes with 1, 2 and 3 subtrees is a specialization of this function:

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

---

Edit: Yes, the datatype above is in fact redundant, since a tree with exactly one leaf x could be written as:

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)

If you remove Empty, this redundancy goes away, but you can no longer represent empty trees. A simple way to overcome this is by using two types:

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 

Or if you prefer fewer constructors and a type composed of pre-existing ones:

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

but this is slightly bothersome.

这篇关于在 SML 中对树进行计数后修改元组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！