# Implementing map with tail recursion

I am trying to solve this exercise. It is about reimplementing the `map` function in haskell for learning purpose. I found a solution which doesn't browse all the elements of the list (simple linked list, so accessing the last element will browse all the list) at each iteration, but I didn't found one which is tail recursive.

``````accumulateRec :: (a -> b) -> [a] -> [b]
accumulateRec func [] = []
accumulateRec func (h:t) = (func h) : accumulateRec func t
``````

Is there a way to implement map in a tail recursive way and without browsing all the list at each iteration ?

PS: exercism.io is an awesome way to learn a new language.

Tail recursion is not a good idea in Haskell with list functions, because tail recursion prevents lazy evaluation from returning a partial result.

But anyway, to answer your question, it is possible to write a "reversed map" function (like `map` except the order of elements is reversed) that is tail-recursive and does not go through the list each step. It maintain an accumulator which is the list of results so far (backwards), and for each new element in the input, it prepends the result to the accumulator (and that's why it's backwards).

``````reverseMap :: (a -> b) -> [a] -> [b]
reverseMap func = helper [] where
helper acc [] = acc
helper acc (h:t) = helper (func h : acc) t
``````

Of course, since you got the results backwards, you need to reverse it again, and since `reverse` is also tail-recursive, the whole operation is tail-recursive.

``````myMap :: (a -> b) -> [a] -> [b]
myMap func = helper [] where
helper acc [] = reverse acc
helper acc (h:t) = helper (func h : acc) t
``````

Haskell is lazy, so in most situations, this function will only be evaluated as far as necessary, and that means that the first thing evaluated will always be the type constructor `:`, since anything that uses the result must first look at the type constructor before it can look at any value inside.
So Haskell first builds a list node containing an unevaluated stub for the value `func h` and an unevaluated stub for the tail `accumulateRec func t`. And only when these values are actually needed will it evaluate these stubs.