Personal tools

Top-level vs. local recursion

From HaskellWiki

Revision as of 00:07, 8 February 2009 by Lemming (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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