在 SML 中查找一棵树的所有有效地址

Question

我想编写一个程序来传递 SML 中简单树的所有有效地址。这种情况下树的数据结构是：

datatype tree = T of tree list

我目前的情况是：

fun address (T ts) = (rev (#2(foldl (fn (s,(sum, liste)) => (sum+1,[sum]::liste) ) (1, [nil]) ts))) @ (map address ts);

我的想法是，foldl 为父节点创建一个包含所有地址的列表，并通过附加所有子节点的地址，最终提供所有可能地址的列表。口译员不同意：

Elaboration failed: Type clash. Functions of type 'a list * 'a list → 'a list cannot take an argument of type int list list * int list list list: Cannot merge int list and int.

有什么想法吗？

Answer 1

那么地址到底是什么？当我想到树中特定节点的地址时，我会想到某种到达该节点的描述。由于您的树是 n-ary，地址可以是索引列表，例如

val someTree =
  T [        (* address: [] *)
    T [],    (* address: [0] *)
    T [      (* address: [1] *)
      T [],  (* address: [1,0] *)
      T []   (* address: [1,1] *)
    ],
    T []     (* address: [2] *)
  ]

因此，如果您的 datatype tree 类型被扩展为在某个节点中保存值，那么知道节点的地址将是导航到正确值的可靠方法。在那之前，这些地址在概念上仍然有意义，尽管它们可能不太有用。

[...] list of all addresses for the parent nodes, and by appending the adresses of all children nodes it eventually delivers the list of all possible adresses.

假设我的解释是正确的，那么是的，你描述的策略很有道理。

您可以从求解树中的单层开始，例如

fun range n = List.tabulate (n, fn i => i)
val zip = ListPair.zip

fun addresses (T ts) =
    let val ts' = zip (ts, range (length ts))
    in ts'
    end

试试这个，

- addresses someTree;
> val it = [(T [], 0), (T [T [], T []], 1), (T [], 2)] : (tree * int) list

应该说

T []，第一个子树，所有子地址都应该以0 : ....
T [T [], T []]，第二个子树，所有子地址都应该以1 : ....
T []，第三个子树，所有子地址都应该以2 : ....

接下来我可能得想办法让addresses为每个子树递归调用自己。如果我们忽略上面的索引添加函数，递归可能看起来像：

fun addresses (T ts) =
    List.concat (List.map (fn t => addresses t) ts)

其中 List.map (fn t => ...) ts 寻址 ts 中的每个子树 T ...。因为 addresses t 本身会生成一些东西的列表，所以 List.map (fn t => addresses t) ts 会生成那些列表的列表。为了避免无限循环类型的列表列表......，List.concat 在每个递归步骤中将 "list of list of ..." 折叠为 "list of ..."。

然而，运行宁此，

- addresses someTree;
! Warning: Value polymorphism:
! Free type variable(s) at top level in value identifier it
> val it = [] : 'a list

非常无用，因为它实际上做除了解决每个节点之外的任何事情。

模式 List.concat (List.map f xs) 很常见，所以让我们创建一个辅助函数来完成这两项操作，因为它会使代码更整洁。另外，让我们尝试将每个子结果的前缀与当前节点的索引和的两种策略结合起来，对每个节点进行完整的递归遍历：

fun range n = List.tabulate (n, fn i => i)
fun concatMap f xs = List.concat (List.map f xs)
val zip = ListPair.zip

fun addresses (T ts) =
    let val ts' = zip (ts, range (length ts))
    in concatMap (fn (t, i) => ...) ts'
    end

现在，... 部分应该都执行 addresses t 以获得子结果列表，每个子结果都是索引列表，并且应该添加 i在每个列表的前面（例如 map (fn addr => i :: addr)）。

假设您解决了这部分，您可能仍然运行生成零结果：

- addresses someTree;
> val it = [] : int list list

这是因为addresses (T [])实际上应该给出[[]]：空树的所有地址列表是到根节点的地址列表，到根节点的地址是（由我）定义为 []。所以 [[]] 将是一个具有指向根节点的单个地址的列表。

解决这个问题，

fun addresses (T []) = [[]]
  | addresses (T ts) = ...

您可以获得所有节点的完整地址列表：

- addresses someTree;
> val it = [[0], [1, 0], [1, 1], [2]] : int list list

我发现 [] 不在此列表中，因此您可能需要添加它。

以上只是一个建议。有很多替代方法可以构建此解决方案。您可以使用显式递归辅助函数构建 addresses，该函数将第二个参数作为索引：

fun addresses (T ts) = ...

and addresses_helper [] _ = []
  | addresses_helper (t:ts) i =
      map (fn addr => ...) (addresses t) @ addresses_helper ts (i+1)

或者您可以将其概括为 foldl / foldr，就像您最初所做的那样。或者你可以定义一个 zipWith 而不是 concatMap (... map ...) (zip ...) 你可以有 concat (zipWith ...):

fun range n = List.tabulate (n, fn i => i)
fun curry f x y = f (x, y)
fun zipWith f (x::xs) (y::ys) = f x y :: zipWith f xs ys
  | zipWith _ _ _ = []
val concat = List.concat

fun addresses (T []) = [[]]
  | addresses (T ts) =
    let fun prefix t i = map (curry op:: i) (addresses t)
    in concat (zipWith prefix ...)
    end

我建议使用基于 concatMap 或 zipWith 的解决方案，而不是使用 foldl / foldr 的解决方案，因为我认为它们更容易读。它们可能会导致一些额外的遍历，因为你使用 foldl / foldr 技术上可以构建 i 因为你正在递归而不是调用 range，但它是以可读性为代价的.

在 SML 中查找一棵树的所有有效地址

Find all valid addresses of a tree in SML

tree

sml