# How expensive is list reversal in Elixir?

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

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

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.

9 Likes

``````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

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`.

1 Like

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

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