递归 ML 函数取消嵌套，仅接受类型为"嵌套列表"的值并返回列表

Question

下面是一个例子示例：

- unnest;
val it = fn : 'a NestedList -> 'a list
(* [1,2,3] *)
- unnest(List [(Atom 1), (Atom 2), (Atom 3)]);
val it = [1,2,3] : int list

我被给予

datatype 'a NestedList =
Nil
| Atom of 'a
| List of 'a NestedList list;

到目前为止我有什么

fun unnest(Nil) = []
| unnest(Atom(x)) = [x] 
| unnest(List(x::xs)) = unnest(x);

它只给出了列表的头部，我不知道如何到达列表的其余部分。我知道有一种使用concat、map和fn的方法，但有没有不使用库函数的方法？

Answer 1

将unnest应用于NestedList值意味着生成一个普通的旧list。所以我们知道这个函数的类型必须是：

'a NestedList -> 'a list

当我们将unnest应用于List时，我们需要将其递归地应用于所包含列表中的每个元素。

你的职能有两个问题。

1. 它不考虑模式匹配中的空列表
2. 它只作用于非空列表中的第一项

如果我们将mapunnest添加到包含列表中的每个元素，我们将获得列表列表。这不是我们最终想要的，但我们可以使用它

fun unnest(Nil) = []
| unnest(Atom(x)) = [x] 
| unnest(List(lst)) = map unnest lst

上面的内容不会编译，因为最后一个案例会产生一个'a list list。我们怎样才能把一个列表变成一个列表呢？

我们可以使用@运算符将两个列表连接起来，这意味着我们可以将其折叠在列表上以获得扁平列表。

fun unnest(Nil) = []
| unnest(Atom(x)) = [x] 
| unnest(List(lst)) = foldl op@ [] (map unnest lst)

评估unnest(List [(Atom 1), (Atom 2), (Atom 3)])现在得到[3, 2, 1]。由于foldl向op@发送参数的顺序不同，所以情况正好相反。如果我们编写一个匿名函数，我们可以纠正这个问题。

fun unnest(Nil) = []
| unnest(Atom(x)) = [x] 
| unnest(List(lst)) = foldl (fn (x, i) => i @ x) [] (map unnest lst)