在 SML 中反转列表

Question

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

为什么我的这个反转列表的功能不起作用

Answer 1

您的函数的类型为

'a list -> 'a list

。

::

的类型为

'a -> 'a list -> 'a list

。因此，您无法将调用

reverse

的结果作为第一个参数传递给

::

。

您可以按照 JRose

 的建议使用

@ ，因为它具有类型

'a list -> 'a list -> 'a list

并将连接两个列表，但与

::

相比效率较低。

是 O(n)。使用它使得

reverse

具有 O(n^2) 运行时效率。

相反，让我们使用尾递归辅助函数以相反的顺序构建累加器列表 using

::

，然后返回它。因为

::

是 O(1)，所以它的运行时效率是 O(n)，比 O(n^2) 很多好。

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

考虑倒车

[1, 2, 3]

：

reverse [1, 2, 3]
aux [1, 2, 3] []
aux [2, 3] [1]
aux [3] [2, 1]
aux [] [3, 2, 1]
[3, 2, 1]

和

::

的效率。链接讲的是 OCaml，但 SML 的核心原理是一样的。