0

我有这个代码：

datatype 'a Tree = Empty | LEAF of 'a | NODE of ('a Tree) list;
val iL1a = LEAF 1;
val iL1b = LEAF 2;
val iL1c = LEAF 3;
val iL2a = NODE [iL1a, iL1b, iL1c];
val iL2b = NODE [iL1b, iL1c, iL1a];
val iL3 = NODE [iL2a, iL2b, iL1a, iL1b];
val iL4 = NODE [iL1c, iL1b, iL3];
val iL5 = NODE [iL4];

fun treeToString f Node = let
    fun treeFun (Empty) = ["(:"]
    | treeFun (NODE([])) = [")"]
    | treeFun (LEAF(v)) = [f v]
    | treeFun (NODE(h::t)) = [""] @ ( treeFun (h)) @ ( treeFun (NODE(t)) )
    in
    String.concat(treeFun Node)
end;

treeToString Int.toString iL5;

当我运行我的函数时，我得到输出：“32123)231)12)))”。

答案应该是“((32((123)(231)12)))”。

我已经尝试修改我的函数以添加 ( 在我能想到的每个地方，但我无法弄清楚我应该在哪里添加 "("。我在哪里搞砸了？

编辑：我相信我需要在某处使用 map 或 List.filter ，但不确定在哪里。

4

1 回答 1

2

看起来您对列表节点尾部的递归方法是问题所在。尝试将其用于 NODE 案例，而不是treeFun h附加到treefun (NODE(t))：

 treeFun (NODE(items)) = ["("] @ List.concat (map treeFun items) @ [")"]

也就是说，映射 节点的全部内容，并用和treeFun包围结果。这个定义可能有点过于简洁，你无法理解发生了什么，所以这里有一个更详细的形式，你可能会发现更清楚："("")"

| treeFun (NODE(items)) =
  let val subtree_strings : string list list = map treeFun items
      val concatenated_subtrees : string list = List.concat subtree_strings
      in ["("] @ concatenated_subtrees @ [")"]
      end

subtree_strings是获取给定节点中的所有子树，并通过递归调用treeFun每个子树将每个子树转换为字符串列表的结果。由于treeFun每次调用它都会返回一个字符串列表，并且我们在整个子树列表上调用它，结果是相应的子树列表列表。例如，如果我们调用map treeFun [LEAF 1, LEAF 2, LEAF 3]，我们会返回[["1"], ["2"], ["3"]]。

这不是我们想要的答案，因为它是字符串列表而不是普通字符串列表。我们可以使用 来解决这个问题List.concat，它接受一个列表列表，并形成一个包含所有基础项目的单个列表。所以例如List.concat [["1"], ["2"], ["3"]]返回["1", "2", "3"]。现在我们所要做的就是在结果周围加上括号，我们就完成了。

请注意，此策略对于完全空的节点与对于具有一个或多个子树的节点一样有效，因此它消除了treeFun原始定义中对第二种情况的需要。通常，在 ML 中，如果一个参数的函数对于该参数类型的每个构造函数都没有完全相同的 case，那么这是一种代码异味。

于 2010-11-07T23:44:27.987 回答