Implementing map with tail recursion

Question

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.

Answer 1

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

Answer 2

Recursive functions in Haskell are tricky business.

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.

Or in other words, in Haskell, any recursive function which uses the recursion result as an argument to a data constructor is probably not actually recursive in the execution model.

The bottom line is that the function you have already has the advantage that tail recursive functions have, namely constant space evaluation instead of building a huge stack of recursions.