Implement tail recursive `map` operation for a list

Questions / Help
,
1

Hello,

As a learning exercise, I’m trying to implement the map operation for a list. My first attempt was:

  def map1([], _), do: []
  def map1([head | tail], f) do
    [f.(head) | map1(tail, f)]
  end

This works, but then I realize this was not tail recursive, because the last operation to happen is prepending an item to the list. I tried to come up with a tail recursive solution, but I can’t find a simple one. I came up with this:

  def map2(list, f), do: do_map(list, f, [])

  def do_map([], f, mapped), do: mapped
  def do_map([head | tail], f, mapped) do
    do_map(tail, f, [f.(head) | mapped])
  end

but this reverses the list. I could re-reverse it afterwards of course, but isn’t there a solution that is tail recursive and does not require post-processing?

2

Since [head | tail] operation is optimized by compiler it’s much faster to simply call reverse (which is second [head | tail] operation) instead of appending item to list like list ++ [item] which is much more expensive.

In case you are not sure which solution is faster consider using this library:

1 Like
3

That’s pretty much exactly what the stdlib function does actually.

-spec map(Fun, List1) -> List2 when
      Fun :: fun((A) -> B),
      List1 :: [A],
      List2 :: [B],
      A :: term(),
      B :: term().

map(F, [H|T]) ->
    [F(H)|map(F, T)];
map(F, []) when is_function(F, 1) -> [].
2 Likes
4

This is a really common idiom for doing recursive transformations:

  # pre-processing: wrapper function that sets up an empty accumulator 
  def map2(list, f), do: do_map(list, f, [])

  # post-processing: reverse the accumulator
  def do_map([], f, mapped), do: Enum.reverse(mapped)

  # recursive processing
  def do_map([head | tail], f, mapped) do
    do_map(tail, f, [f.(head) | mapped])
  end

For many additional examples, see the Elixir stdlib - for instance, in Enum:

3 Likes
5

Yes, but that is O(n²) (or was it even worse?)…

def map([], _, acc), do: acc
def map([h|t], f, acc), do: map(t, f, acc ++ [f.(h)])