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