Top-level vs. local recursion

Compare the following two implementations of map. The first one uses top-level recursion

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

whereas the second one uses local recursion

map :: (a -> b) -> [a] -> [b]
map f =
   let go []     = []
       go (x:xs) = f x : go xs
   in  go

Although the first version is shorter, there some reasons to prefer the second version for stylistic reasons:

• It clearly shows that the 'f' is not "altered" in the recursion.
• You cannot accidentally 'jump' into the wrong loop. I often have multiple implementations of the same function which differ in laziness or performance. They only differ slightly in name and it happened too often that after copy&paste the recursive call went to a different (and thus wrong) function.
• The local loop is probably also more efficient in execution, because the compiler does not need to move the f around. However, if this is actually more efficient then the compiler should do such a transformation itself.

Btw. the best implementation is probably foldr (\x acc -> f x : acc) [] which is both short and allows deforestation.

See also

• Haskell-Cafe on HLint 1.2