时间戳

首页 > 解决方案 > Elixir 中的尾调用优化

elixir - Elixir 中的尾调用优化

问题描述

清除尾调用优化的概念所需的帮助很少。据我了解，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

标签： elixir

解决方案

是的，您的两个示例都是 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，因为您可能会破坏堆栈。否则，您可能只是通过编写 TCO 函数为自己节省一些堆栈空间和额外的 GC 运行。

推荐阅读