Is it better during recursion to do `list ++ [add_this]` or rather proper `[add_this | list]` and finish with `Enum.reverse/1`?

Questions / Help
,
1

Hi all,

I wrote this litle snippet:

  @spec map_tuples_and_stop_on_error(list, {:error | :ok, list}, fun) :: {:error | :ok, list}
  def map_tuples_and_stop_on_error([], {result, elements}, fun)
    when result in [:error, :ok] and is_list(elements) and is_function(fun),
    do: {result, Enum.reverse(elements)}

  def map_tuples_and_stop_on_error([first | rest], {result, elements}, fun)
    when result in [:error, :ok] and is_list(elements) and is_function(fun) do
    case fun.(first) do
      {:error, _} = result -> result
      {:ok, add_this} -> map_tuples_and_stop_on_error(rest, {:ok, [add_this | elements]}, fun)
    end
  end

  test "map_tuples_and_stop_on_error" do
    fun = &if &1 >= 100, do: {:error, :too_much}, else: {:ok, &1 + 1}

    assert MyModule.map_tuples_and_stop_on_error([1, 2, 3, 4, 5], {:ok, []}, fun) == {:ok, [2, 3, 4, 5, 6]}

    assert MyModule.map_tuples_and_stop_on_error([95, 96, 97, 98, 99], {:ok, []}, fun) == {:ok, [96, 97, 98, 99, 100]}

    assert MyModule.map_tuples_and_stop_on_error([97, 98, 99, 100, 101], {:ok, []}, fun) == {:error, :too_much}

    assert MyModule.map_tuples_and_stop_on_error([99, 100, 101, 102, 103], {:ok, []}, fun) == {:error, :too_much}
  end

It’s like a map but it works only with functions that return {:error | :ok, any} and it doesn’t return error / ok tuples. Instead of returning list of {:ok, value} it returns list with value elements or first error tuple.

When I was writing this code I realized I can add a new element into a list using slow / improper method

elements ++ [add_this]

or just using the proper / fast method

[add_this | elements]

and at the end finish the recursion with Enum.reverse(elements).

Could you please tell me, would you recommend the fast method + reverse or the slow method without reverse?

Thank you.

Kind regards,
Mat

2

Do not append in a loop/recursion to the accumulating value, that will make your loop/recursion of O(n²) or worse, while "cons"ing and then reversing will make it O(n).

3 Likes
3

In other words I should keep the code as it is since appending items into a list (by merging two lists) is sooo bad from perf. reasons and depends on list size which makes the operation exponentially more costly. Thank you ;-).

Btw. could you please tell me what O stands for?
It’s either recursion r, iteration i, loop l or element e so I wonder…

4

Sorry, it’s “big-O” notation. A measure of worst case complexity for algorithms.

1 Like
5

No need to apologize. :wink: I’m one of those programmers without required mathematical knowledge so I should apologize. Thank you.

6

It’s not required, though as in my closer environment all programmers do have at least a minimal formal education in the area, I often forget that this is not the default.

Basically O(1) means, that the complexity is constant and size of the input doesn’t change it.
O(n) means that complexity rises linearly with the inputs size.
And finally O(n²) means, that if you double the input, it will quadruple the complexity.

There are more classes, though explain this 3 usually makes one understand the concept and makes one able to read.

1 Like
7

That makes sense, thank you.

I might get there thanks to learning Haskell. This year (and this decade ;-)) my second language (after Elixir). “Thank you” C19 lockdown.

1 Like
8

I don’t think O is a core concept in haskell.

It’s more of a data structures/algorithms concept, not a type theory concept.