如何使用 sml 编写函数将 2 元组列表转换为扁平列表？

Question

我遇到了一个问题，需要将元组列表转换为扁平列表，例如：

[(1,2), (3,4), (5,6)] 可以变成 [1,2,3,4,5,6]

我试过写这样的函数：

fun helper2(nil,b) = []
|   helper2(a,nil) = []
|   helper2(a::l1,b::l2) =l1::l2

fun flatten2 [] = []
|   flatten2 ((a,b)::tl) = helper2(a,b)

显示：

val flatten2 = fn : ('a list * 'a list list) list -> 'a list list

当我尝试运行它使用命令 flatten2[(1,2),(3,4),(5,6)]; 它会给我以下错误信息：

stdIn:1.2-1.29 Error: operator and operand do not agree [overload conflict]
  operator domain: ('Z list * 'Z list list) list
  operand:         ([int ty] * [int ty]) list
  in expression:
    flatten2 ((1,2) :: (3,4) :: (<exp>,<exp>) :: nil)

我的问题是：

为什么 SML 将 a 和 b 值视为列表，而不仅仅是 a 和 b
我如何修改我的代码，以便 SML 可以将 a 和 b 视为 'a 和 'b 而不是列表
如何使此代码按应有的方式工作？

谢谢

Answer 1

第一个问题：至于类型为什么会出现('a list * 'a list list)，是因为类型推断正在查看这部分代码：

|   helper2(a::l1,b::l2) =l1::l2
                            ^^
                           here

请记住 "cons" (::) 运算符的类型是 'a -> 'a list -> 'a list，它将 单个元素 粘贴到相同类型元素的列表。所以 SML 得出结论，无论 l1 和 l2 是什么，关系是 l2 是 l1 是什么的列表。

fun helper2(nil,b) = []

说 a 必须是一个列表，因为 nil 的类型是 'a list。因此，l2 必须是列表的列表（某种类型 'a）。

问题 2 和 3：我不太确定如何更正所编写的代码。我可能会这样写：

fun helper2 [] accum = List.rev accum
|   helper2 ((a,b)::tl) accum =  helper2 tl (b :: a :: accum);

fun flatten2 list = helper2 list [];

helper2 完成所有脏活。如果输入列表为空，那么我们就全部完成了，我们可以 return 我们一直在构建的反向 accumulator。第二种情况是我们实际向累加器添加东西。我们在列表的头部和尾部进行模式匹配。此模式匹配意味着输入的类型为 ('a * 'a) list（两个元素类型相同的元组列表）。在头部，我们有一个元组，我们分别将第一个和第二个元素命名为 a 和 b。我们将 a 然后 b 添加到累加器上，并在列表的尾部递归调用 helper2。最终，我们将遍历列表中的所有元素，然后只剩下累加器——回想一下，它包含所有元素，但顺序相反。调用 List.rev 反转累加器，这就是我们的答案。

当我加载运行时，我得到了这个：

- flatten2 [(1,2), (3,4), (5,6)];
val it = [1,2,3,4,5,6] : int list

Answer 2

Why SML see the a and b values as lists, not just simply a and b

克里斯已经深入回答了这个问题。

您将 a 作为第一个参数传递给 helper2，它需要一个列表作为其第一个参数。您将 b 作为第二个参数传递给 helper2，后者使用其第二个参数 b::l2，也是一个列表，作为列表的尾部，其中 a 是头部。所以 b 必须是这些列表的列表。

这没有任何意义，很可能是语法混乱的结果：您在 flatten2 中传递了您认为的单个元素 a 和 b ，但是当您在 helper2 中处理它们时，它们现在是列表，其中头部称为 a 和 b。 a 和 b.

不一样

How can I revise my code so SML can see a and b as 'a and 'b not lists

您可以放弃辅助函数：

fun flatten2 []             = []
  | flatten2 ((a,b)::pairs) = a :: b :: flatten2 pairs

有辅助函数的目的是为了在递归时累加结果，因为这个版本flatten2使用了很多堆栈space。它可以用一个额外的参数来做到这一点，这样 flatten2 就不需要提及它了：

这是克里斯制作的版本。

How to make this code work the way it should be?

您可以通过多种方式编写此代码。提到了两种使用显式递归的方法。

这里有一些使用高阶函数的替代方法：

(* Equivalent to my first version *)
fun flatten2 pairs =
  foldr (fn ((a,b), acc) => a :: b :: acc) [] pairs

(* Equivalent to Chris'es version *)
fun flatten2 pairs =
  rev (foldl (fn ((a,b), acc) => b :: a :: acc) [] pairs)

(* Yet another alternative *)
fun concatMap f xs =
  List.concat (List.map f xs)

fun flatten2 pairs =
  concatMap (fn (a,b) => [a,b]) pairs

如何使用 sml 编写函数将 2 元组列表转换为扁平列表？

How to use sml to write a function to turn a list of 2-tuples to a flattened list?

function

list

sml