I personally prefer Enum functions chained together, for instance:

  def enum_chain(items, y) do
    new_ys =
      [y | Enum.scan(items, y, fn item, acc -> item.height + acc end)]

    items
    |> Enum.zip(new_ys)
    |> Enum.map(fn {item, new_y} -> %{item | y: new_y} end)
  end

This produces a little more garbage to collect, due to intermediate results - but each step has a clear responsibility and is readable at a glance (assuming you remember Enum.scan )

If items is large, you could avoid that garbage generation by using Stream:

  def stream_chain(items, y) do
    new_ys =
      Stream.concat([y], Stream.scan(items, y, fn item, acc -> item.height + acc end))

   items
   |> Stream.zip(new_ys)
   |> Enum.map(fn {item, new_y} -> %{item | y: new_y} end)
  end

In this case there are drop-in Stream replacements for Enum functions, so the code doesn’t materially change. This implementation trades off performance for efficiency: no intermediate values to GC but longer runtime because Stream uses lots of anonymous functions.

In order to benchmark such questions, what other items should I consider in addition to the average execution time?

You may look at Benchee, it’s great.

That being said, is there any situation where ++ is the right choice for working with lists?

When you are mapping / reducing over a list, it’s alway better not to use ++. But sometimes you get a list from elsewere and the only thing you have to do with it is to append. In that case the better choice is ++. This operator is not forbidden A general rule of thumb is “do not use ++ in a loop, only once.”

Is there a better solution to this problem?

I find that your map_reduce implementation is the cleanest of all. There may be other solutions but I would just use the more readable. A tip though: you can put the clauses matching on [] (empty list) below the clause matching on items. There is no need to try this clause at each loop iteration.

Is it always better to write recursive functions in general than to use Enum functions?

I think that “better” depends on what you want. If you need the best performance, then custom recursive function should be faster. If you want clean code, I think Enum.map() is better as you will separate the logic from the unpacking/repacking of the list items. For reduce() it depends.

Does Beam perform a special optimization in the recursion/2 function that is written in the code, which performs better than tail_recursion_with_reverse/2?

There is this note in erlang docs:

A tail-recursive function that does not need to reverse the list at the end is faster than a body-recursive function, as are tail-recursive functions that do not construct any terms at all (for example, a function that sums all integers in a list).

source.

In your case, you have reverse, so it is not certain that it will be faster than the body-recursive function.

@mpope

[1, 2, 3] ++ [4]

Only a single element suffers from the left hand copy in that case.

I don’t think so. This snippets builds a new list like this : [1|[2|[3|[4]]]], it re-builds the full list of 4 items. This is why ++ is generally avoided, because it creates a copy of the left-hand list. If you need to concat 2 lists then it is fine, but it is not recommended to append a few items to a large list.

You might not need to

From the efficiency guide

Pattern matching in function head as well as in case and receive clauses are optimized by the compiler. With a few exceptions, there is nothing to gain by rearranging clauses.

There seems to be some gotchas and edge cases, but most of the time this should make no difference.

For point 2, using ++ is relatively cheap when adding a new element to the end of a list, such as:

[1, 2, 3] ++ [4]

Only a single element suffers from the left hand copy in that case.

As for recursion out performing tail_recursion_with_reverse, there is the overhead of the reverse to consider. That is one less n length operation that the function needs to perform. I suggest you checkout The Seven Myths of Erlang Performance. They explain the history behind the assumption that tail recursion is more performant.

As for question 3, I personally prefer pure recursive functions over the standard libraries when the task is simple. The recursion function is simple and elegant. But that is personal preference, and optimization should only be done after measurement in production, so any of the above solutions will be fine in most scenarios.

As for question 1, I’d suggest trying Streams, and maybe ParallelStream, and also trying a recursive solution with a preallocated tuple instead of a list accessed with element/2. Could get a speedup from the spacial cache locality.

Also as a note, function calls and pattern matching aren’t ‘free’. It looks like recursion uses the least amount of both function calls and branches. That could give things a boost as well.

Nice benchmark!

Thanks for the explanation and links. I need to read about Stream and ParallelStream.