list - 如何使用 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)

我的问题是:

1. 为什么 SML 将 a 和 b 值视为列表，而不仅仅是 a 和 b
2. 我如何修改我的代码，以便 SML 可以将 a 和 b 视为“a 和”b 而不是列表
3. 如何使这段代码按应有的方式工作？

谢谢

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 完成所有脏活。如果输入列表为空，那么我们就全部完成了，我们可以返回我们一直在构建的反向累加器。第二种情况是我们实际向累加器添加东西。我们在列表的头部和尾部进行模式匹配。此模式匹配意味着输入的类型为 ('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