Difference between revisions of "Top-level vs. local recursion"

From HaskellWiki
Jump to: navigation, search
m
m (Minor formatting changes)
 
Line 16: Line 16:
   
 
Although the first version is shorter, there are reasons to prefer the second version for stylistic reasons:
 
Although the first version is shorter, there are reasons to prefer the second version for stylistic reasons:
* It clearly shows that the 'f' is not "altered" in the recursion.
+
* It clearly shows that the <hask>f</hask> is not "altered" in the recursion.
* You cannot accidentally jump into the wrong loop. I often implement the same function more than once for comparison. The implementations may differ in laziness or performance. Their names are only slightly different and it happened too often that after copy&paste&name-change the recursive call went to the original (and thus wrong) function.
+
* You cannot accidentally jump into the wrong loop. I often implement the same function more than once for comparison. The implementations may differ in laziness or performance. Their names are only slightly different and it happened too often that after ''copy&paste&name-change'' the recursive call went to the original (and thus wrong) function.
 
* The local loop is probably also more efficient in execution, because the compiler does not need to move the <hask>f</hask> around. However, if this is actually more efficient then the compiler should do such a transformation itself.
 
* The local loop is probably also more efficient in execution, because the compiler does not need to move the <hask>f</hask> around. However, if this is actually more efficient then the compiler should do such a transformation itself.
   

Latest revision as of 23:02, 18 April 2021

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 are 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 implement the same function more than once for comparison. The implementations may differ in laziness or performance. Their names are only slightly different and it happened too often that after copy&paste&name-change the recursive call went to the original (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