两种递归函数的区别

Question

在 OCaml 中，我见过有两种编写

map

函数的方法

let rec map f xs =
  match xs with
  | [] -> []
  | x::rest -> f x :: map f rest

和

let map f xs =
  let rec go xs = 
    match xs with
    | [] -> []
    | x::rest -> f x :: go rest
  in go xs

第二个看起来更优化，因为它类似于循环不变消除，但在函数式编程中它可能涉及分配一个新的闭包。谁能解释两种递归函数风格之间的区别，特别是在性能方面？感谢您的帮助！

我在SO中找不到类似的问题，我希望有一个像“递归不变消除”这样的术语来描述从第一个程序到第二个程序的转换。

Answer 1

我一直想知道完全相同的事情：编译器是否优化递归函数中的不变参数？ 既然你的问题促使我对其进行基准测试，那么让我在这里分享我的结果。

协议

我还没有尝试过

map

，因为它需要大列表，这会导致 stack_overflow。我可以用

rev_map

尝试一下，但我看不到分配巨大列表的意义，而在整数上测试等效行为更容易（而且我担心分配。最终会触发一轮 GC，这会弄乱我的时间测量）。

以下代码使用带有不变参数的虚拟递归函数重现您的用例，如

map

中所示：

let rec g f x = if x = 0 then 0 else g f (f x)

let g2 f x =
  let rec aux x = if x = 0 then 0 else aux (f x) in
  aux x

let time title f x =
  let t = Sys.time () in
  let fx = f x in
  Printf.printf "%s: %fs\n%!" title (Sys.time () -. t) ;
  fx

let main =
  let nb = int_of_string Sys.argv.(1) in
  ignore (time "normal" (g pred) nb) ;
  ignore (time "invariant elimination" (g2 pred) nb)

您可以编译它（例如

ocamlopt a.ml

）并通过执行以下操作来运行它

./a.out 10000000000

。显然，您可以更改整数参数来调整递归调用的次数。

结果

在我的电脑上，输入数字10000000000，输出：

normal: 11.813643s
invariant elimination: 11.646377s

关于更大的值：

20000000000

normal: 23.353022s
invariant elimination: 22.977813s

30000000000

normal: 35.586871s
invariant elimination: 35.421313s

我懒得去更高的地方。 在我看来，这似乎表明两个版本是等效的，也许编译器确实优化了递归函数中的不变参数，但它只是不可测量，也许不是。

字节码比较

我还尝试查看生成的字节码是否相同（ocamlc -dinstr a.ml），并且它确实略有不同，正如您在下面的代码片段中看到的那样

正常

编译一个仅包含以下内容的文件：

let g f x =
  let rec aux f x = if x = 0 then 0 else aux f (f x) in
  aux f x

给予

    branch L2
    restart
L3: grab 1
    acc 1
    push
    const 0
    eqint
    branchifnot L4
    const 0
    return 2
L4: acc 1
    push
    acc 1
    apply 1
    push
    acc 1
    push
    offsetclosure 0
    appterm 2, 4
    restart
L1: grab 1
    closurerec 3, 0
    acc 2
    push
    acc 2
    push
    acc 2
    appterm 2, 5
L2: closure L1, 0
    push
    acc 0
    makeblock 1, 0
    pop 1
    setglobal E!

不变消除

编译一个仅包含以下内容的文件：

let g2 f x =
  let rec aux x = if x = 0 then 0 else aux (f x) in
  aux x

给出：

    branch L2
L3: acc 0
    push
    const 0
    eqint
    branchifnot L4
    const 0
    return 1
L4: acc 0
    push
    envacc 1
    apply 1
    push
    offsetclosure 0
    appterm 1, 2
    restart
L1: grab 1
    acc 0
    closurerec 3, 1
    acc 2
    push
    acc 1
    appterm 1, 4
L2: closure L1, 0
    push
    acc 0
    makeblock 1, 0
    pop 1
    setglobal E2!

但是我不够专业，无法得出任何结论，因为我不会说字节码。 也正是在这里，我决定现在答案并不那么重要，无论如何，下次我见到他时问@gasche会更容易。

Answer 2

使用

go

表明有 Haskell 背景。 OCaml 和 Haskell 都是函数式编程语言，但存在实质性差异，人们对 Haskell 的了解不应该用来对 OCaml 做出假设。

我认为没有特别的理由以第二种方式写

map

。如果您使用 OCaml 4.14.0 或更高版本，您可能需要使用

tail_mod_cons

使

map

尾递归，而不需要显式累加器，如 Stef 的评论中所示。

let[@tail_mod_cons] rec map f = 
  function 
  | [] -> [] 
  | x::xs -> f x :: map f xs

当然，真正的解决方案是：

let map = List.map

List.map

实现 与上面非常简单的实现类似，但进行了一些调整以确保评估顺序并使

tail_mod_cons

更高效。

let[@tail_mod_cons] rec map f = function
    [] -> []
  | [a1] ->
      let r1 = f a1 in
      [r1]
  | a1::a2::l ->
      let r1 = f a1 in
      let r2 = f a2 in
      r1::r2::map f l

Answer 3

和其他人一样，我从未见过第二种形式。而且我很难想象它能提供什么样的优化。然而我知道的是（正如 @Stef 和 @Chris 指出的）这个函数可以用尾递归的方式编写。所以只是为了完整起见：

let map f xs =
  let rec go xs ys =
    match xs with
    | [] -> ys
    | x::rest -> go rest ((f x)::ys)
  in List.rev (go xs [])

此版本比您帖子中的两种形式更加优化，因为每个下一个递归调用都可以重用相同的堆栈帧，从而消除不必要的分配，节省空间和执行时间。