如何在 ML 中创建平面列表函数?
How do I create a flatlist function in ML?
我得到了一个练习,要求我编写一个函数 flatlist
,它接受一个列表列表,并 "flattens" 通过返回原始列表中所有列表的串联。
例如:
flatlist([1,2], [6,7], [9]) = [1,2,6,7,9]
下面的代码是我试过的
fun flatlist([]) = []
| flatlist(a::rest) = (a::rest);
我在编写函数时没有收到错误消息,但在 REPL 中尝试该函数并在示例中应用该函数时遇到问题。
要求您编写的函数通常称为 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")。
我得到了一个练习,要求我编写一个函数 flatlist
,它接受一个列表列表,并 "flattens" 通过返回原始列表中所有列表的串联。
例如:
flatlist([1,2], [6,7], [9]) = [1,2,6,7,9]
下面的代码是我试过的
fun flatlist([]) = []
| flatlist(a::rest) = (a::rest);
我在编写函数时没有收到错误消息,但在 REPL 中尝试该函数并在示例中应用该函数时遇到问题。
要求您编写的函数通常称为 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")。