SML/ML Int 到 String 的转换

Question

我有这样的代码：

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 ，但不确定在哪里。

Answer 1

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

 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 的第二种情况的需要。一般来说，在机器学习中，如果一个参数的函数对于该参数类型的每个构造函数没有完全相同的一种情况，那么这就是一种代码味道。