Best way to attack the back end of a list?

Questions / Help
1

I’m a beginner to Elixir, so please correct me if my understanding is incorrect. But it appears that while Elixir has some nice tools for parsing from the front end of a list, it is lacking for tools to parse the back end of a list.

hd()                      --> List.last()
tl()                      --> Enum.slice(list, 0, length(list) - 1)
|  (to build lists)       --> ++ (slower for really long lists)
| (pattern matching)      --> nothing

Moreover some of these equivalent tools like List.last and Enum.slice can’t be used in guards.

With that in mind, I’m wondering if the best option is just to work with the list backwards, and then reverse it as the final step. So if you have a tail recursive function with an accumulator, you’d have this as your “when the list is empty” function clause.

foofun([], acc), do: Enum.reverse(acc)

What do you all think?

2 Likes
2

Yep this is a good way to do it

1 Like
3

Also keep in mind

def foofun([head | tail], acc) do
  ...
  foofun(tail, acc)
end

rather than using Kernel.hd/1 or Kernel.tl/1.

Furthermore once you get used to thinking recursively don’t be shy to make use of anything that implements Enumerable.reduce/3 like Enum.reduce/3.

That being said don’t get too fixated on the Enum module - if you find that you need multiple passes through a collection have a look at the Stream module. With it you can set up a pipeline of operations and have the last stage “pull the data through” without repeatedly iterating through the collection (Elixir Getting Started: Enumerables and Streams).

1 Like
4

The reason for this lack of symmetry is that the data structure itself - a list is not symmetrical.

Accessing front of the list is a very easy and fast operation (it’s constant time - O(1)). On the other hand accessing the back of the list requires walking the entire list until the end is reached - it’s a complicated and slow operation (linear to the length of the list - O(n)).

When building a list in a loop the usual approach is to prepend and reverse at the end, exactly as you proposed.

2 Likes
5

Note: Since this is such a common operation, the underlying VM has special code to make reversing the list as fast as possible. However, this reversing trick only works for List. There are other kind of Enumerables for which Enum.reverse requires tranversing the entire Enumerable
to first convert it to a List.

If you look in

You will see many examples of :lists.reverse from Erlang used to optimize the final step of a reduction.

1 Like
6

To be clear, Enum.reverse has a fast path for lists which calls :lists.reverse. Thus, Enum.reduce on lists is just as fast as :lists.reverse.

4 Likes
7

Thanks for all the great responses, that definitely answers my question and then some.