Elixir中的尾部调用优化

Question

小编需要帮助大家理清Tail call优化的概念。据我所知 Tail call optimisation 只有当你调用一个递归函数作为你的最后一条语句时才有效。下面是我的2个例子，我不确定这两个例子是否都是尾部调用优化的。

有一个中间结果变量

    def map(list, fun) do
        do_map(list,fun,[])
    end
    defp do_map([],_fun,result) do
        result
    end
    defp do_map([h|t],fun,_result) do
        result = fun.(h)
        do_map(t,fun,result)
    end
end 

没有中间的结果变量。它是否会被认为是 Tail call optimised ?

defmodule MyList do
    def map(list, fun) do
        do_map(list,fun,[])
    end
    defp do_map([],_fun,result) do
        result
    end
    defp do_map([h|t],fun,_result) do
        do_map(t,fun,fun.(h))
    end
end

Answer 1

是的，你的两个例子都是TCO，因为递归函数 do_map 是 最后一次手术，因为在Elixir中所有的参数都是先被评估的。使其不成为TCO的唯一方法是在最终操作之前调用递归函数。

有TCO。

defmodule MyList do
  def map(list, fun) do
    do_map(list, fun, [])
  end
  defp do_map([], _fun, result) do
    Enum.reverse(result)
  end
  defp do_map([h|t], fun, result) do
    do_map(t, fun, [fun.(h) | result])
  end
end

没有TCO:

defmodule MyList do
  def map(list, fun) do
    do_map(list, fun)
  end
  defp do_map([], _fun) do
    []
  end
  defp do_map([h|t], fun) do
    # The final call is the list append operation
    [fun.(h) | do_map(t, fun)]
  end
end

请记住，Erlang中的尾部调用优化的函数 不一定快. 在erlang中，TCO的主要目的是由于它在 循环处理诸如 gen_server's enter_loop.

如果您的功能 从来没有 回归，那么你 必须 来使用TCO，因为你可以炸掉堆栈，否则你可能只是为自己节省一些堆栈空间和额外的GC运行。否则你可能只是通过编写TCO函数为自己节省一些栈空间和额外的GC运行。