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

Question

我正在尝试在SML中编码并面对以下列出的问题 我制作了N-Ary树并且变量tr存储了创建的树的值。

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

功能猫是什么，我希望将打印所有的叶子节点的值。 但我得到一个非详尽的搜索警告，它不起作用。

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]的模式，以免末尾有任何杂散空间。以下作品：

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"]] 

是完全有效的。案例cat (node [x]) = cat x旨在剥离那些毫无意义的中间节点。在最后一个子句中巧妙的是，如果xs是树列表，那么它本身不是树，所以它必须在构造函数node中被包装，然后才被送到cat。

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与一个硬连线分隔符（“”）和树数据类型中节点列表的特殊情况。