Appending a list to a literal list efficiently

Questions / Help
1

Hi! I’m learning Elixir and this is my first post here.

I understand the underlying structure of a list. It’s a linked list, everything is immutable, best way to add to a list is to the head. I also understand some of the tricks to join lists in an efficient manner.

My question, though, is if you’re creating a new list, is there a way to efficiently join a literal list with an existing list. It seems like it should be possible. Basically, it should be possible to create the literal list with the last item just pointing to the existing list.

The closest I could come up with (and perhaps help demonstrate what I’m talking about) is this:

list = [4, 5]
new_list = [1 | [2 | [3 | list]]]

That’s obviously going to be a terrible to read syntax.

Perhaps something like [1, 2, 3] ++ list is already optimized in the way I’m describing? I’m not sure how to check.

1 Like
2

:wave:

AFAIK these two are equivalent:

iex> [1 | [2 | [3 | list]]]
[1, 2, 3, 4, 5]

iex> [1, 2, 3 | list]
[1, 2, 3, 4, 5]
2 Likes
3

There we go! I figured it must be possible. Somehow I got it into my head that it was only [head | tail] and didn’t realize there was more options. Thanks!

1 Like
4

ah… now I have a follow-up question… My specific use-case was actually a keyword list. It seems like the following doesn’t work:

list = [fa: 4, so:5]
new_list = [do: 1, ray: 2, me: 3 | list]

However, I can do it the long way by doing new_list = [{:do, 1}, {:ray, 2}, {:me, 3} | list].

Is there any way to do this with a keyword list with less typing?

1 Like
5

You can safely use ++ here. It is no different on literals.

3 Likes
6

FWIW, appending to a keyword list may not be what you want - functions like Keyword.get will return the first matching element, so prepending allows the values from the literal to be overridden.

Example:

base_list = [foo: 1, bar: 2, baz: 3]
input_list = [bar: 42]

output_1 = base_list ++ input_list
Keyword.get(output_1, :bar) # => 2

output_2 = input_list ++ base_list
Keyword.get(output_2, :bar) # => 42
1 Like
7

Do you require any special treatment of duplicated keys?

1 Like
8

You can safely use ++ here. It is no different on literals.

Maybe my explanation wasn’t the best… My issue is that I’d like it do something better than a basic new_list = list_a ++ list_b. If you just do that, then you have to rebuild list_a and then have the last list item point to list_b. If you’re using a literal, you’re building the list right there and could just build it with the last list item pointing to list_b. In other words, not first create list_a and then throw it out to create new_list.

I’m assuming doing [1, 2, 3 | list] does this, but I’m not sure how to know definitively. I was hoping to do the same thing with a “keyword list”, but maybe the syntactic sugar just isn’t there.

9

Do you require any special treatment of duplicated keys?

I need to keep duplicates and retain the order. I’m working with a library that’s wanting values to be passed in as a nested keyword list. I’m creating the first part of the list as a literal and then want to append another keyword list at the end.

This was more about the fact that I know it’s a linked list and I was hoping there was a simple way to build the literal list where the final list item just pointed to the list I wanted to append to the end. Building the list with the final item as the terminal and then building it all over again with the final item pointing to the other list seems unnecessary.

10

With a literal value on the left, using ++ and using | are byte code identical. They compile to the same thing.

EDIT: if it isn’t a literal, you should still use ++. It is optimized properly by the VM. The only thing to avoid is appending in a loop. In that case prepend and then reverse.

4 Likes
11

IMO you are over-focusing on implementation details and perceived optimizations. As @benwilson512 points out, the BEAM VM is handling these scenarios as best as it can, and Erlang docs are very open about the performance woes of singly-linked lists.

I know this is not what you asked but in case you want to take inspiration from it and/or your needs morph in the future – you could take a look at Erlang’s queue module.

12

I realize I’m focusing on small details, but I find it helpful to have a firm grasp on how things are working “under the hood”.

With a literal value on the left, using ++ and using | are byte code identical. They compile to the same thing.

Great! I figured the compiler would/could properly optimize that, but wasn’t sure. Google searches weren’t coming up with anything.

2 Likes
13

https://www.erlang.org/doc/system/commoncaveats.html#operator

3 Likes
14

also have a look at:

Erlang only supports fast prepends to lists while appending requires a full copy. Getting the size of a list is also aO(n) operation. This library implements a deque using two rotating lists to support fast append and prepend as well as O(1) size via an internal counter.

1 Like