SML n 叉树中的非详尽搜索错误

Question

我正在尝试使用 SML 编写代码并遇到下面列出的问题我做了一个 N-Ary 树，变量 tr 存储创建的树的值。

val tr =node([leaf "x", node([leaf "y", leaf "x" , leaf "z"])]);

函数 cat 是我希望打印所有叶节点的值的函数。但是我收到了非详尽搜索警告，但它不起作用。

fun cat (node ( [node t1 , node t2])) = cat(node t1) ^" "^cat(node t2) | cat ( node ([leaf x, node t1])) = x ^" "^cat(node t1) | cat( leaf x) = x

这是我的 n 叉树数据结构

datatype 'a ntree = leaf of 'a | node of 'a ntree list;

得到错误如下

 `val tr = node [leaf "x",node [leaf "y",leaf "x",leaf "z"]] : string ntree
 .\printValues.sml:14.5-16.20 Warning: match nonexhaustive
      node (node t1 :: node t2 :: nil) => ...
      node (leaf x :: node t1 :: nil) => ...
      leaf x => ...

  val cat = fn : string ntree -> string
  - cat(tr);

  uncaught exception Match [nonexhaustive match failure]
   raised at: .\printValues.sml:16.20`
  `

我该如何解决这个问题？相反，请指出如何继续调试它的方向。

Answer 1

您缺少 cat (node xs) 的定义，其中 xs 的元素少于 2 个。

node 模式只是底层的列表——所以您应该遵循基本的 SML 模式在列表上定义函数，方法是为空列表提供定义，然后为看起来像的模式提供定义x::xs。在您的情况下，您可能希望单独处理看起来像 node [x] 的模式，以免最后有任何杂散的 space 。以下作品：

fun cat (leaf x) = x
|   cat (node []) = ""
|   cat (node [x]) = cat x
|   cat (node (x::xs)) = cat x ^ " " ^ cat (node xs);

我向上移动了 leaf x 模式——因为对我来说这是一个基础案例，并且按照惯例，基础案例列在最前面。树定义的一个特点是它允许非分支父节点。例如，

node[node[leaf "x"]]

完全有效。 case cat (node [x]) = cat x 的目的是去除那些有些毫无意义的中间节点。最后一个子句中的一个巧妙之处在于，如果 xs 是一个树列表，那么它本身并不是一棵树，因此在被馈送到 cat 之前必须将其包装在 node 构造函数中。

SML 并不完全包括电池 -- 但 Standard ML Basis Library 有一些好东西。有一个 String.concatWith 是一个 join 函数。如果你可以使用它，那么有一种巧妙的方式来写你想要的东西：

fun cat (leaf x) = x
|   cat (node branches) = String.concatWith " " (map cat branches);

样本输出：

cat tr;
val it = "x y x z" : string

第一种方法可以被认为是使用硬连线分隔符 (" ") 定义类似 concatWith 的内容，并且在树数据类型中的节点列表的特殊情况下。

SML n 叉树中的非详尽搜索错误

Non exhaustive search error in SML n-ary tree

sml

smlnj