我想递归地获取 2 元组的列表(例如 [(1， 2(， (3， 4(， (5， 6(]( 并将其转换为两个整数列表的元组(结果： ([1， 3， 5]， [2， 4， 6]( (。我知道如何做相反的事情(将两个列表的元组转换为元组列表(，但我不明白如何对同一列表进行递归调用。
这是我到目前为止的代码，我认为我很接近：
fun toTuple [] = ([], [])
| toTuple [((x:int, y:int)::xs)] = (x::[], y::[]) toTuple (xs).
编译器给了我错误：
Error: operator is not a function [tycon mismatch]
operator: int list * int list
in expression:
(x :: nil,y :: nil) unzip
我相信这意味着我需要在 (x：：[]， y：：[]( 和 toTuple (xs( 之间放置一个运算符。我希望递归将元组项目放入我创建的同一列表中，但我不知道运算符可以做这样的事情。
谢谢。
我会使用显式累加器参数来做到这一点：
fun loop (xs, ys, nil) = (rev xs, rev ys)
| loop (xs, ys, (x, y) :: zs) = loop (x :: xs, y :: ys, zs)
fun toTuple xs = loop (nil, nil, xs)
事后看来，以下方法会更有效：
fun loop (xs, ys, nil) = (xs, ys)
| loop (xs, ys, (x, y) :: zs) = loop (x :: xs, y :: ys, zs)
fun toTuple xs = loop (nil, nil, rev xs)
以下是使用普通递归函数执行此操作的方法：
fun toTuple [] = ([], [])
| toTuple ((x,y)::pairs) =
case toTuple pairs of
(xs, ys) => (x::xs, y::ys)
它以递归方式处理剩余的pairs，将结果解压缩为(xs, ys)，然后向该结果添加x和y。您可以使用 let 绑定，而不是大小写：
fun toTuple [] = ([], [])
| toTuple ((x,y)::pairs) =
let val (xs, ys) = toTuple pairs
in (x::xs, y::ys)
end
如果你没有直接在函数toTuple中执行这种模式匹配，你可能不得不将结果的解包和重新打包移动到一个单独的函数中：
fun add (x,y) (xs,ys) = (x::xs, y::ys)
fun toTuple [] = ([], [])
| toTuple (pair::pairs) = add pair (toTuple pairs)
这三种方法或多或少是等效的。
针对@pyon的尾递归变体，
fun loop (xs, ys, nil) = (rev xs, rev ys) | loop (xs, ys, (x, y) :: zs) = loop (x :: xs, y :: ys, zs) fun toTuple xs = loop (nil, nil, xs)当我试图更多地了解该语言时，请问为什么使用第二个函数？是为了使它更简单并传入最终将成为返回元组的第一部分和第二部分的两个空值吗？另外，绝对有没有办法在不使用辅助函数的情况下做到这一点？您的解决方案将起作用，但我想更多地了解这个问题。
如果你将我的三个解决方案与pyon的解决方案进行比较，他的解决方案在某些方面是不同的：他有一个递归的帮助函数loop，而我用辅助函数编写的版本add，add不是递归的，只管理解包和重新打包元组。toTuple仍然只有一个参数，但loop还有两个参数，一个用于存储临时结果x :: xs，一个用于y :: ys。
当您从左到右处理列表，但在参数中累积结果时，输入中的第一个元素将成为第一个添加到累积结果中的元素，这意味着它最终成为结果的最后一个元素。(您可以在此处将列表视为堆栈。
当累积结果是应该与输入顺序相同的元素列表时，这并不那么幸运。您可以通过手动评估函数来最好地看到这一点：
首先，对于我的toTuple [(1,2),(3,4),(5,6)]版本：
toTuple [(1,2),(3,4),(5,6)]
~> case toTuple [(3,4),(5,6)] of
(xs, ys1) => (1::xs1, 2::ys)
~> case (case toTuple [(5,6)] of
(xs', ys') => (3::xs', 4::ys')) of
(xs, ys) => (1::xs, 2::ys)
~> case (case (case toTuple [] of
(xs'', ys'') => (5::xs'', 6::ys'')) of
(xs', ys') => (3::xs', 4::ys')) of
(xs, ys) => (1::xs, 2::ys)
~> case (case (case ([], []) of
(xs'', ys'') => (5::xs'', 6::ys'')) of
(xs', ys') => (3::xs', 4::ys')) of
(xs, ys) => (1::xs, 2::ys)
~> case (case (5::[], 6::[]) of
(xs', ys') => (3::xs', 4::ys')) of
(xs, ys) => (1::xs, 2::ys)
~> case (3::5::[], 4::6::[]) of
(xs, ys) => (1::xs, 2::ys)
~> (1::3::5::[], 2::4::6::[]
~> ([1,3,5], [2,4,6])
第二，对于@pyon的版本：
toTuple [(1,2),(3,4),(5,6)]
~> loop ([], [], [(1,2),(3,4),(5,6)])
~> loop (1::[], 2::[], [(3,4),(5,6)])
~> loop (3::1::[], 4::2::[], [(5,6)])
~> loop (5::3::1::[], 6::4::2::[], [])
~> (rev [5,3,1], rev [6,4,2])
~> ...
~> ([1,3,5], [2,4,6])
编辑：正如@pyon在评论中指出的那样，这些使用相同的内存和时间。区别在于我的版本使用隐式(调用(堆栈，而他的版本使用显式(参数(堆栈。