时间戳

首页 > 解决方案 > 在 SML 中查找树的所有有效地址

tree - 在 SML 中查找树的所有有效地址

问题描述

我想编写一个在 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 为父节点创建所有地址的列表，并通过附加所有子节点的地址，它最终提供所有可能地址的列表。口译员不同意：

详细说明失败：类型冲突。类型的函数'a list * 'a list → 'a list不能接受类型的参数int list list * int list list list：不能合并int list和int。

那么有什么想法吗？

标签： treesml

解决方案

那么究竟什么是地址呢？当我考虑到树中特定节点的地址时，我会想到某种关于到达该节点的描述。由于您的树是n元，因此地址可以是索引列表，例如

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

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

[...]父节点的所有地址列表，并通过附加所有子节点的地址，最终提供所有可能地址的列表。

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

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

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每个子树T ...。ts因为addresses t它本身会产生一个列表，所以List.map (fn t => addresses t) ts会产生一个列表。为了避免无限循环类型的列表列表类型...，List.concat在每个递归步骤中将该“列表列表...”折叠为“...列表”。

然而，运行这个，

- 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到每个列表的前面（例如 with 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就像您最初所做的那样。或者你可以定义一个zipWithand 而不是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

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

推荐阅读