SML使用reduce和map遍历一棵n叉树

SML using reduce and map to traverse an n-ary tree

我是 SML 新手。

假设我有以下数据类型：

datatype 'a tree = leaf of 'a | node of 'a tree list

和函数val leaves = fn : 'a tree -> 'a list:

fun leaves (leaf x) = [x]
  | leaves (node []) = []
  | leaves (node [x]) = leaves x
  | leaves (node (x::xs)) = (leaves x) @ (leaves (node xs))

如果我有

val t = node [node [leaf 1,
              node [leaf 2, leaf 3],
              leaf 4]];

那么，leaves t会return[1, 2, 3, 4]给我。

我想问的是，这个可以用reduce和map重写吗？

鉴于减少：

fun reduce g [x] = x
  | reduce g (x::xs) = (g x (reduce g xs))

非常感谢。

您似乎经常以过多的子句开头。

从两个必要的开始：

fun leaves (leaf x) = [x]
  | leaves (node xs) = ???

现在，xs 是一个列表。
map 将一个列表转换为另一个列表。
reduce 将列表缩减为单个值。

这表明您想要某种形式的东西

| leaves (node xs) = reduce f (map g xs)

确定 f 和 g 作为练习。

在 ML 中有一个约定，不是由 SML 中的语法强制执行，即数据构造函数以大写字母开头，值（包括函数）以小写字母开头。在模式匹配中，这使它们更容易区分，因为在语法上，node 可以是数据构造函数或变量，如果不检查整个代码就无法分辨。

Whosebug 倾向于同意我们的看法，因为它的语法高亮显示不是很好 [=7​​7=] 并且除非我们遵循此约定，否则无法为数据构造函数绘制特殊颜色。

所以：

datatype 'a tree = Leaf of 'a | Node of 'a tree list

molbdnilo 已经展示了如何将 leaves 中的模式简化为两个：

fun leaves (Leaf x) = [x]
  | leaves (Node ts) = ???

（请注意，我更改了构造函数的大小写并将 xs 重命名为 ts，因为它是一个树列表。）

要使用递归来完成这个功能，我会说你可以在这里采用两种方式。正如你将看到的，两个方向都有trade-offs，我会提到：

  • 坚持使用两种模式并在单独的、相互递归的函数中处理 xs 上的递归：

    fun leaves (Leaf x) = [x]
  | leaves (Node ts) = nodes ts

and nodes [] = []
  | nodes (t::ts) = leaves n @ nodes ts

    拥有两个可以相互调用的函数只是一点点 mind-bending。你必须不断提醒自己 t 是一棵树，所以 leaves 应该被调用，但是 ts 是一个树列表，所以 nodes 应该被调用那。但是除了在后续的相互递归函数中使用 and 而不是 fun 之外，语法还不错。

  • 转到三个模式并通过匹配两级深度来处理树及其内部列表的递归：

    fun leaves (Leaf x) = [x]
  | leaves (Node []) = []
  | leaves (Node (t::ts)) = leaves t @ leaves (Node ts)

    只有一个函数似乎更简单，但缺点是模式匹配变得有点棘手：您不只是匹配输入是 Node，而是具体地说它是 Node 没有 children (Node []) 或至少有一个 child (Node (t::ts)) 的节点。这里的复杂性在于，当您成功进行模式匹配以解构可以递归传递给 leaves (leaves t) 的单个 t 时，处理 ts 的其余部分（一个 'a tree list), 你没有处理这样一个列表的函数。但你几乎做到了：如果你把 Node 放回 ts (Node ts)，你会得到一个 'a tree 和 child 节点列表。而你有处理一棵树的功能。

随着时间的推移，您可以自己决定哪个想法更难处理。

也许在不同的场合你都喜欢。

What I want to ask is that, does this is possible to be rewritten by using reduce and map?

是的。