How expensive is list reversal in Elixir?

To be honest, I don’t know whether it is O(n) or O(1). I have a feeling that it is O(n). I’d be happy if someone more experienced chimes in.

At the same time, I did an exercise on Exercism recently that required a “fast” solution. It required working with a list of 1_000_000 items and reversing the list was fast enough. Reversing through tail recursion. I think that Enum.reverse uses a similar approach if not something faster :).

List reversal is indeed O(n) , however it is also a built in optimized function within the VM. List reversal happens constantly within functional languages, so the VM goes to a lot of effort optimize it.

About Your question about “better solution” then when building binaries the answer almost always will be the same - io lists.

defmodule RomanNumerals do
  @digits [
    {1000, "M"},
    {900, "CM"},
    {500, "D"},
    {400, "CD"},
    {100, "C"},
    {90, "XC"},
    {50, "L"},
    {40, "XL"},
    {10, "X"},
    {9, "IX"},
    {5, "V"},
    {4, "IV"},
    {1, "I"}
  ]
  @doc """
  Convert the number to a roman number.
  """
  @spec numeral(pos_integer) :: String.t()
  def numeral(n), do: do_numeral(n, [])

  defp do_numeral(0, list), do: List.to_string(list)

  for {n, d} <- @digits do
    defp do_numeral(n, list) when n >= unquote(n),
      do: do_numeral(n - unquote(n), [list | unquote(d)])
  end
end

This is a fascinating solution

Can you explain the use of unquote() in this context? I don’t think I’ve seen it outside of a defmacro quote.

There is “implicit macro” which is in def/defp. You can think about unquote/1 in this case as a way to use variable from “outer scope”:

defmodule Foo do
  foo = 1

  def foo, do: unquote(foo)
end

Foo.foo #=> 1

So in this sense it is a way to use bindings defined in for comprehension within function definition. It is used to have dynamically defined functions via meta programming. And sometimes it is required to be able to use custom atom as function name:

defmodule Foo do
  def unquote(:"foo-bar"), do: 42
end

Which is sometimes needed for modules that are meant to work for example with xmerl or '$handle_undefined_function'/2 handler, ex:

defmodule Foo do
  def unquote(:"$handle_undefined_function")(f, a), do: IO.inspect({f, a})
end

Foo.bar

Thanks, very helpful! So the overloading of variable n is just coincidence? It’s unclear to me how the compiler knows that the n passed to unquote() is from the outer scope. Or perhaps, by calling unquote() you are telling the compiler that n can only be from the outer scope?

Yes, in this case it can be only from the outer scope as “function” n do not exists at all. It would probably be more clear if I would write it as:

  for {num, roman} <- @digits do
    defp do_numeral(n, list) when n >= unquote(num),
      do: do_numeral(n - unquote(num), [list | unquote(roman)])
  end