如何在 ML 中创建平面列表函数？

Question

我得到了一个练习，要求我编写一个函数 flatlist，它接受一个列表列表，并 "flattens" 通过返回原始列表中所有列表的串联。

例如：

flatlist([1,2], [6,7], [9]) = [1,2,6,7,9]

下面的代码是我试过的

fun flatlist([]) = []
  | flatlist(a::rest) = (a::rest);

我在编写函数时没有收到错误消息，但在 REPL 中尝试该函数并在示例中应用该函数时遇到问题。

Answer 1

要求您编写的函数通常称为 concat 并且碰巧以名称 List.concat 存在于标准库中。尽管如此，编写这样的递归函数仍然是一个很好的练习。你的函数确实进行了类型检查和编译，除了有一个你还没有发现的细微缺陷。

关于语法的一些东西

首先，关于白色 space 和括号，我可能会以不同的方式格式化您的第一次尝试：

(* Before *)
fun flatlist([]) = []
  | flatlist(a::rest) = (a::rest);

(* After *)
fun flatlist [] = []
  | flatlist (xs :: xss) = xs :: xss

这里遇到的要点是：

由于第一个元素本身就是一个列表，所以我喜欢给它取一个复数名称，xs，而由于其余的是事物列表的列表，我喜欢给它是一个双复数的名字。但是 xs :: rest 也可以。只是为了避免将 reader 与 x 混淆，后者是表示单个任意值的好名称。
[] 模式周围的括号不是必需的，因为 [] 是单个组合符，因此不需要消除歧义。但是，模式 xs :: xss does 需要在其周围加上括号，因为它包含一个采用多个参数的中缀模式构造函数。如果我们把它排除在外，就像这样：
```
fun flatlist [] = []
  | flatlist xs :: xss = xs :: xss
```
我们会收到以下警告（在 Moscow ML 中）：
```
! Toplevel input:
!   | flatlist xs :: xss = xs :: xss
!                 ^^
! Ill-placed infix in a fun clause
```
xs :: xss函数体周围的括号，另一方面，没有需要括号，因为函数体在语法上是为单个表达式保留的，xs :: xss。这里不需要消歧。
结尾的 ; 也不是绝对必要的，除非您将此函数复制粘贴到 REPL 中而不是将其放入文件中。因此，只要您的函数非常短，您只需将它们复制粘贴到 REPL 中进行试用，使用 ; 就可以了。当您开始构建更大的函数并一次执行整个文件时，您最好将它们排除在外。

这里的主要收获，也与您将此函数应用于值时遇到的问题有关，可能来自您使用函数应用程序的编程语言的经验 f(x)括号的意思是“前面是函数名，中间是它的参数。

SML 函数不同：最简单形式的函数应用看起来像 f x。需要括号来消除歧义，例如 f (x + 2) 与 (f x) + 2，但不需要它们来表示这是函数应用程序。函数名称和值之间的 space 会处理这个问题。

正在分析您的初始解决方案

您遇到的第一个问题是将列表列表传递给函数。在您的示例中，您实际上正在做的是传递一个 3 元组，(x,y,z) 与 x、y 和 z 是列表。此值的类型是 int list * int list * int list，而不是函数 flatlist 期望的 int list list。这是因为SML中的括号，当里面有逗号的时候，是用来表示元组，而不是"arguments to a function".

尝试整数列表的列表，这反而给出：

- flatlist [[1,2], [6,7], [9]];
> val it = [[1, 2], [6, 7], [9]] : int list list

多田！等等

让我们通过一次减少表达式的一部分来手动评估您对 flatlist 的第一次尝试，看看发生了什么。在这里，我一次导出一行函数调用 ⇒ 意思是 "reduces to":

  flatlist [[1,2], [6,7], [9]]          (* x = [1,2], xs = [[6,7], [9]] *)
⇒ [1,2] :: flatlist [[6,7], [9]]        (* x = [6,7], xs = [[9]] *)
⇒ [1,2] :: [6,7] :: flatlist [[9]]      (* x = [9], xs = [] *)
⇒ [1,2] :: [6,7] :: [9] :: flatlist []  (* base case *)
⇒ [1,2] :: [6,7] :: [9] :: []           (* just another way to write *)
⇒ [[1,2], [6,7], [9]]

因此您当前的 flatlist 是一个非常复杂的 identity function 列表。

正确解决方案的提示

所以你有基本的递归权利，但是你需要在每个递归状态下执行的操作有点偏离。它不仅仅是 xs :: xss 作为函数体，因为它会产生与输入完全相同的输出。您必须以某种方式将列表 xs 的元素与下一个列表的元素连接起来，对 xss.

中的所有列表递归

提示：@ 运算符（发音为 "append"）。

如何在 ML 中创建平面列表函数？

How do I create a flatlist function in ML?

sml

ml

关于语法的一些东西

正在分析您的初始解决方案

正确解决方案的提示