# Implement tail recursive `map` operation for a list

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
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
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?

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

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

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
For many additional examples, see the Elixir stdlib - for instance, in `Enum`:
``````def map([], _, acc), do: acc