CODEWITHSUNDEEP
elixir
Khubaib Ahmad
Khubaib Ahmad

Reputation: 49

Tail call optimisation in Elixir

Little help needed on clearing the concept of Tail call optimisation. As far as i understand Tail call optimisation only works when you call a recursive function as your last statement. Here are my 2 examples and i am not sure if both are tail call optimised or not.

With an intermediate result variable

    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

WITHOUT an intermediate result variable. Will it be considered as 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

Upvotes: 2

Views: 249

Answers (1)

lastcanal
lastcanal

Reputation: 2175

Yes, both examples of yours are TCO because the recursive function do_map is the last operation, as all arguments in Elixir are evaluated first. The only way to make it not TCO is by calling the recursive function before the final operation.

With 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

Without 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

Keep in mind that Tail Call Optimized functions in Erlang might not always be faster. The main purpose of TCO in erlang is due to it's use in process top-loops, such as gen_server's enter_loop.

If your function never returns then you must to use TCO as you can blow the stack. Otherwise you might just be saving yourself some stack space and additional GC runs by writing TCO functions.

Upvotes: 2

Related Questions