How expensive is list reversal in Elixir?

Questions / Help
1

One of the Exercism exercises on the Elixir track is to take an integer (0 to ~3000) and convert it to a Roman numeral. My solution was a little “pipe-happy,” and I have subsequently discovered better approaches. In the course of doing all that piping, I used Enum.reverse() twice. I’ve read that sometimes list reversal is O(n) and sometimes O(1) with a pointer swap, but I don’t know which applies in Elixir. Should I even care? Or perhaps a better question, at what length of list should I start caring?

For reference, my solution:

defmodule RomanNumerals do
  @doc """
  Convert the number to a roman number.
  """
  @spec numeral(pos_integer) :: String.t()
  def numeral(number) when is_integer(number) do
    number
    |> Integer.digits()
    |> Enum.reverse()
    |> Enum.with_index()
    |> Enum.map(&get_roman/1)
    |> Enum.reverse()
    |> List.to_string()
  end

  def get_roman({_number, _index} = pair) do
    case pair do
      {0, _} -> ""
      {1, 0} -> "I"
      {2, 0} -> "II"
      {3, 0} -> "III"
      {4, 0} -> "IV"
      {5, 0} -> "V"
      {6, 0} -> "VI"
      {7, 0} -> "VII"
      {8, 0} -> "VIII"
      {9, 0} -> "IX"
      {1, 1} -> "X"
      {2, 1} -> "XX"
      {3, 1} -> "XXX"
      {4, 1} -> "XL"
      {5, 1} -> "L"
      {6, 1} -> "LX"
      {7, 1} -> "LXX"
      {8, 1} -> "LXXX"
      {9, 1} -> "XC"
      {1, 2} -> "C"
      {2, 2} -> "CC"
      {3, 2} -> "CCC"
      {4, 2} -> "CD"
      {5, 2} -> "D"
      {6, 2} -> "DC"
      {7, 2} -> "DCC"
      {8, 2} -> "DCCC"
      {9, 2} -> "CM"
      {1, 3} -> "M"
      {2, 3} -> "MM"
      {3, 3} -> "MMM"
      _ -> "Too High!"
    end
  end
end

And a more elegant solution by one of the other students:

defmodule RomanNumerals do
  @doc """
  Convert the number to a roman number.
  """
  @spec numeral(pos_integer) :: String.t()
  def numeral(n) do
    cond do
      n >= 1000 -> "M"  <> numeral(n - 1000)
      n >= 900  -> "CM" <> numeral(n - 900)
      n >= 500  -> "D"  <> numeral(n - 500)
      n >= 400  -> "CD" <> numeral(n - 400)
      n >= 100  -> "C"  <> numeral(n - 100)
      n >= 90   -> "XC" <> numeral(n - 90)
      n >= 50   -> "L"  <> numeral(n - 50)
      n >= 40   -> "XL" <> numeral(n - 40)
      n >= 10   -> "X"  <> numeral(n - 10)
      n >= 9    -> "IX" <> numeral(n - 9)
      n >= 5    -> "V"  <> numeral(n - 5)
      n >= 4    -> "IV" <> numeral(n - 4)
      n >= 1    -> "I"  <> numeral(n - 1)
      true      -> ""
    end
  end
end
1 Like
2

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 :).

1 Like
3

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.

12 Likes
4

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
4 Likes
5

This is a fascinating solution :slight_smile:

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

1 Like
6

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
4 Likes
7

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?

8

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
5 Likes