使用递归来反转Ocaml中的列表

Question

我试图使用递归来反转列表（不改变它）与辅助函数，没有匹配或折叠。目标：

# let list1 = ["a"; "b"; "c"; "d"; "e"];;
val list1 : string list = ["a"; "b"; "c"; "d"; "e"]
# listreverse list1;;
- : string list1 = ["e"; "d"; "c"; "b"; "a"]

我的代码：

let rec helper remainder reversed =  
if remainder  = [] then reversed else List.hd remainder :: (helper (List.tl remainder) reversed);;

let listreverse lst = helper lst [];;

但是，目前这只会返回相同的列表而不会反转它。似乎将头部添加到列表的后面是我的问题。是否有任何小的修复我可以做这个反向列表？

Answer 1

您总是将空列表作为reversed传递，并将输入的第一个元素添加到递归结果的前面。

让我们通过一个小测试案例 - 扭转[1;2]。

这是helper [1;2] []，和

   helper [1;2] []
—> if [1;2]  = [] then [] else List.hd [1;2] :: (helper (List.tl [1;2]) [])
-> List.hd [1;2] :: (helper (List.tl [1;2]) [])
—> 1 :: (helper [2] [])
—> 1 :: (if [2]  = [] then [] else List.hd [2] :: (helper (List.tl [2]) []))
—> 1 :: (List.hd [2] :: (helper (List.tl [2]) []))
—> 1 :: 2 :: (helper [] [])
—> 1 :: 2 :: if []  = [] then [] else List.hd [] :: (helper (List.tl []) [])
—> 1 :: 2 :: []
—> [1;2]

考虑一副牌。 拿顶卡，把它放在桌子上。 然后拿第二张卡并将其放在第一张卡的顶部。 如果你继续这样做，直到第一个牌组为空，你将有一个“新”牌组，其顺序与第一个牌组相反。

辅助函数的要点正是这个原则 - 你可以通过将它们从remainder“移动”到reversed来反转元素，递归调用应该是一个“尾调用” - 也就是说，它只返回结果而不做任何事情它。

let rec helper remainder reversed =  
    if remainder = [] 
    then reversed 
    else helper (List.tl remainder) (List.hd remainder :: reversed)

然后

   helper [1;2] []
—> if [1;2] = [] then []    else helper [2] [1]
—> if [2]   = [] then [1]   else helper []  [2;1]
—> if []    ≈ [] then [2;1] else helper []  ...
—> [2;1]

Answer 2

也许要考虑的问题是，为什么你的辅助函数有两个参数？

您的计划似乎是使用一个参数来构建结果，而另一个参数表示原始列表末尾的未处理部分。

如果这是计划，那么您应该在结尾返回结果（当原始列表为空时）。但是您的代码返回一个空列表。

第二个观察是，如果要将结果作为辅助函数的参数进行构建，则不需要向辅助函数返回的结果添加任何内容。