Concat/appending lists

Chat / Discussions
1

Got a question about when to concat vs. prepending items to list then reversing to achieve appending.

So i know lists boil down to [1 | [2 | []]]. I also know that i can append to a list using something such as

iex(1)> list = [1, 2, 3]
[1, 2, 3]
iex(2)> list ++ [4]
[1, 2, 3, 4]

and I can prepend to a list such as

iex(3)> [4 | list]
[4, 1, 2, 3]

But to achieve what I did before on the line above, i would have to reverse the list, prepend, then reverse again. What if i tried to append a list of items? why would the fastest way be to use something such as Enum.concat or using the ++ to stitch together the two lists and not doing a recursive call that will do just prepend the bits and flip the entire list?

1 Like
2

Enum.concat/2 for two lists is implemented as:

  @spec concat(t, t) :: t
  def concat(left, right) when is_list(left) and is_list(right) do
    left ++ right
  end

:slight_smile:

3 Likes
3

In 99% of the code I write performance is not important so I just use whichever is more expressive for the data I have. For example, compile-time list concatenation? Hell yeah use ++.

However, I believe many general libraries (and the enum module itself in some list building methods) take a prepend then reverse strategy. You’ll see that if you search for Enum.reverse in the elixir code.

1 Like
4

Down in erlang, reversing a list executes a heavily optimized native BIF (built-in-function) because it’s a frequently used feature, so it’s probably not as expensive as you think. That being said, unless your lists are long or you’re in a performance critical part of code, don’t worry too much. Do what’s most expressive.

But if you do need to optimize, be sure to benchmark. For some length of list and algorithm append may be faster, but if the length of the list changes, then prepend-then-reverse may be faster.

I find many times the ordering does not have bearing on the correctness of the code. In those cases I prepend out of habit.

3 Likes
5

Thank you all for the comments. I think i was just overthinking it…

6

It’s very good to be curious – shows intellect. :smiley:

IMO make a very small Elixir project where you benchmark all the approaches you can think of – and with differently sized lists. benchee is an excellent library for this.

Definitely do satisfy your curiosity but also do measure because often you’d end up quite surprised.

And, in real projects, absolutely go for what’s more readable as others said.

3 Likes
7

Or you can look at the fast-elixir benchmark which breaks down the various techniques by list size.

5 Likes
8

That’s a great resource. Based on the results with respect to this question, it makes me wonder why Enum.concat/1 is implemented the way that it is.

9

Because it removes one level of nesting, for any kind of enumerable.

1 Like
10

In general, you should always append to the front of the list and reverse list only when needed, as often one will need to append to list much more often than reading it in order. This is one of the improvements that I have introduced in Sentry some time ago, as breadcrumbs were constructed much more often than these were used (only in case of error).

2 Likes
11

Say what now? You worked at Sentry?

12

No, I have introduced that change in Sentry’a Elixir client. Sentry itself is written in Python.

1 Like