# Best way to attack the back end of a list?

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

Yep this is a good way to do it

1 Like

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

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

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

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

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