如何在 SML 中将第一个列表中的元素与第二个列表中的所有元素配对？
How do I pair the elements in the first list with all the elements in a second list in SML?
问题陈述：编写一个函数 pair，它接受两个整数列表并生成一个对列表，其中每个对是每个列表中每个元素的组合。
例如，pair ([1,2], [3,4,5]) 应该 return
[(1,3), (1,4), (1,5), (2,3), (2,4), (2,5)].
我目前的工作：
-fun pair(a:int list, b:int list) = if null a then nil else if null b then nil else (hd a, hd b)::pair(a, tl b)@pair(tl a, b);
val pair = fn : int list * int list -> (int * int) list
-pair([1,2],[3,4,5]);
val it = [(1,3),(1,4),(1,5),(2,5),(2,4),(2,5),(2,3),(2,4),(2,5)]
我试图跟踪函数以找出 (2,5)、(2,4)、(2,5) 出现的原因，但我仍然看不清楚。
看起来很简单，但我似乎无法解决最后的问题。一些帮助查明为什么在中间添加这些元素会有所帮助。
谢谢。
彼得
由于这是一个练习，我不会向您展示问题陈述的答案。
您要生成的称为两个列表的笛卡尔积。
您当前的方法（格式更好一些），
fun pair (a, b) =
if null a then nil else
if null b then nil else
(hd a, hd b) :: pair (a, tl b) @ pair (tl a, b);
会产生重复的结果，因为您在 pair (a, tl b) 中遗漏了 hd b 并且在 pair (b, tl a) 中遗漏了 hd a，但是在例如的第二次迭代中pair (a, tl b)，a 的第一个元素对 tl b 的每个剩余元素再次处理一次。
您可以通过 一次 处理每个元素来避免这种重复工作。我建议您查看函数 map 和 concat。一般方法是这样的：对于 a 的每个元素 x，为 b 的每个元素 y 生成 (x,y)。 "For every element" 是 map。并且
map (fn x => ...something with (x,y)...) a
生成 列表 结果，如您所愿。但是，如果您重复 map (fn y => ...) b 与 ...something with (x,y)... 部分相同的方法，您将 运行 陷入一个不便的惊喜，而 concat 可以帮助您。
您可以在不使用 map 和 concat 的情况下使用手动递归来解决此练习，但是您可能必须将工作拆分为两个函数，因为您需要一个折叠的函数在 a 的 x 上，并且对于每个 x，在 b 上折叠一次。函数 map 采用了这两个函数共有的递归部分，让您只编写它们不共有的部分。
主要问题是您要对两个列表进行递归。
如果你看看你的例子，
pair ([1,2], [3,4,5]) -> [(1,3), (1,4), (1,5), (2,3), (2,4), (2,5)]
你会看到它有两个子列表，
[(1,3), (1,4), (1,5)]
[(2,3), (2,4), (2,5)]
其中第一个由 [1,2] 的第一个元素和 [3,4,5] 的每个元素形成的对组成，第二个是 [1,2] 的第二个元素也与每个元素配对[3,4,5].
请注意，每个子列表包含所有 [3,4,5] 但仅包含 [1,2] 的一个元素 - 第一个与 pair ([1], [3,4,5]) 相同，第二个是 pair ([2], [3,4,5]) - 所以你应该只需要递归第一个列表。
您可以像这样创建这样的列表：
- 如果任何输入列表为空，则结果为空。
- 否则：
- 取
a 的第一个元素并将其与列表中 b 的每个元素配对（提示：考虑 map。）
- 从
a 的尾部和 b. 的所有尾部递归生成对
- 合并 1 和 2 的结果。
有模式匹配：
fun pair ([], _) = []
| pair (_, []) = []
| pair (x::xs, ys) = <something involving x and ys, suitably combined with 'pairs (xs, ys)'>
如果您将步骤 1 编写为单独的函数，可能会有所帮助。
问题陈述：编写一个函数 pair，它接受两个整数列表并生成一个对列表，其中每个对是每个列表中每个元素的组合。
例如，pair ([1,2], [3,4,5]) 应该 return
[(1,3), (1,4), (1,5), (2,3), (2,4), (2,5)].
我目前的工作：
-fun pair(a:int list, b:int list) = if null a then nil else if null b then nil else (hd a, hd b)::pair(a, tl b)@pair(tl a, b);
val pair = fn : int list * int list -> (int * int) list
-pair([1,2],[3,4,5]);
val it = [(1,3),(1,4),(1,5),(2,5),(2,4),(2,5),(2,3),(2,4),(2,5)]
我试图跟踪函数以找出 (2,5)、(2,4)、(2,5) 出现的原因，但我仍然看不清楚。
看起来很简单，但我似乎无法解决最后的问题。一些帮助查明为什么在中间添加这些元素会有所帮助。
谢谢。
彼得
由于这是一个练习，我不会向您展示问题陈述的答案。
您要生成的称为两个列表的笛卡尔积。
您当前的方法（格式更好一些），
fun pair (a, b) =
if null a then nil else
if null b then nil else
(hd a, hd b) :: pair (a, tl b) @ pair (tl a, b);
会产生重复的结果，因为您在 pair (a, tl b) 中遗漏了 hd b 并且在 pair (b, tl a) 中遗漏了 hd a，但是在例如的第二次迭代中pair (a, tl b)，a 的第一个元素对 tl b 的每个剩余元素再次处理一次。
您可以通过 一次 处理每个元素来避免这种重复工作。我建议您查看函数 map 和 concat。一般方法是这样的：对于 a 的每个元素 x，为 b 的每个元素 y 生成 (x,y)。 "For every element" 是 map。并且
map (fn x => ...something with (x,y)...) a
生成 列表 结果，如您所愿。但是，如果您重复 map (fn y => ...) b 与 ...something with (x,y)... 部分相同的方法，您将 运行 陷入一个不便的惊喜，而 concat 可以帮助您。
您可以在不使用 map 和 concat 的情况下使用手动递归来解决此练习，但是您可能必须将工作拆分为两个函数，因为您需要一个折叠的函数在 a 的 x 上，并且对于每个 x，在 b 上折叠一次。函数 map 采用了这两个函数共有的递归部分，让您只编写它们不共有的部分。
主要问题是您要对两个列表进行递归。
如果你看看你的例子，
pair ([1,2], [3,4,5]) -> [(1,3), (1,4), (1,5), (2,3), (2,4), (2,5)]
你会看到它有两个子列表，
[(1,3), (1,4), (1,5)]
[(2,3), (2,4), (2,5)]
其中第一个由 [1,2] 的第一个元素和 [3,4,5] 的每个元素形成的对组成，第二个是 [1,2] 的第二个元素也与每个元素配对[3,4,5].
请注意，每个子列表包含所有 [3,4,5] 但仅包含 [1,2] 的一个元素 - 第一个与 pair ([1], [3,4,5]) 相同，第二个是 pair ([2], [3,4,5]) - 所以你应该只需要递归第一个列表。
您可以像这样创建这样的列表：
- 如果任何输入列表为空，则结果为空。
- 否则：
- 取
a的第一个元素并将其与列表中b的每个元素配对（提示：考虑map。） - 从
a的尾部和b. 的所有尾部递归生成对
- 合并 1 和 2 的结果。
- 取
有模式匹配：
fun pair ([], _) = []
| pair (_, []) = []
| pair (x::xs, ys) = <something involving x and ys, suitably combined with 'pairs (xs, ys)'>
如果您将步骤 1 编写为单独的函数，可能会有所帮助。