functional-programming - 如何从数据类型中提取元组？

Question

SML 新手，正在尝试通过一系列练习来学习。我正在尝试编写的函数涉及展平具有 N 个子节点的树。我的方法是简单地获取当前的 NTreeNode 并将其值添加到我将返回的某个列表中。然后获取它的第二个参数，即子列表，并将其附加到另一个列表，这将是我的队列。该队列将作为我仍然需要处理的所有项目。

我尝试通过将 NTreeList 和我将使用 flattenNTree 中的初始值返回的列表传递给辅助函数来实现此方法。

但是，当我尝试处理队列中的 NTreeNode 时，它会返回一个 NTree 并且我无法使用我的 first/second 函数，我需要从队列返回一个元组。我只是不明白如何取回元组，我尝试使用 NTreeNode 构造函数，但即使这样也给了我一个 NTree 。

我的问题是如何从我定义的 NTree 数据类型中提取元组。

datatype NTree =
NTreeNode of int * NTree list
| EmptyNTree
;

fun first  (a, _) = a;
fun second (_, b) = b;

fun processTree queue finalList  = 
  if null queue
   then finalList
  else processTree ((tl queue)@(second(NTreeNode(hd queue)))) finalList@[first (NTreeNode (hd queue)) ]
;
fun flattenNTree EmptyNTree = []
   | flattenNTree (NTreeNode x) = processTree (second x) [(first x)]
 ;

输入值示例:

val t =
  NTreeNode (1, [
    NTreeNode (2, [
      NTreeNode (3, [EmptyNTree]),
      NTreeNode (4, []),
      NTreeNode (5, [EmptyNTree]),
      EmptyNTree
    ]),
    NTreeNode (6, [
      NTreeNode (7, [EmptyNTree])
    ])
  ]);

Answer 1

使用模式匹配来分解事物比摆弄诸如 first 或 tl 这样的选择器要容易得多。

反向累积列表并在完成后修复该列表比重复追加到列表末尾更有效。

fun processTree [] final = reverse final
  | processTree (EmptyTree::ts) final = processTree ts final
  | processTree ((NTreeNode (v,t))::ts) final = processTree (ts @ t) (v :: final)