SML列表反转函数求助：为何我的实现无法正常工作？

先看你写的代码：

fun reverse ( [] ) = ( [] )
  | reverse (x::xs) = reverse (xs) :: [x]

问题出在递归分支的运算符使用错误：

• SML中的::运算符作用是把单个元素添加到列表的头部，它要求左边必须是单个元素，右边是列表。
• 但你递归调用reverse(xs)返回的是一个完整的列表（比如反转后的子列表），不是单个元素，用::把它和[x]组合，会导致结果变成嵌套的列表，而不是扁平的反转列表。

举个例子，调用reverse [1,2,3]的过程会生成[[[[],3],2],1]，完全不是预期的[3,2,1]。

修正方案 #

你需要用列表拼接运算符@来替代::，@的作用是把两个列表合并，两边都要求是列表：

fun reverse [] = []
  | reverse (x::xs) = reverse xs @ [x]

如果追求更高的效率（@每次拼接都要遍历左侧列表，时间复杂度O(n²)），可以用带累加器的尾递归版本，时间复杂度是O(n)：

fun reverse lst =
    let
        fun rev_helper [] acc = acc
          | rev_helper (x::xs) acc = rev_helper xs (x::acc)
    in
        rev_helper lst []
    end

内容的提问来源于stack exchange，提问作者Aaryuman Sawai