Editing Haskell programming tips/Discussion (section)

=== Avoid recursion ===

Many times explicit recursion is the fastest way to implement a loop.
e.g.
<haskell>
loop 0 _ acc = acc
loop i v acc = ...
</haskell>

Using HOFs is more elegant, but makes it harder to reason about space usage,
also explicit recursion does not make the code hard to read - just explicit
about what it is doing.

-- EinarKarttunen

I disagree with this.  Sometimes explicit recursion is simpler to design, but I don't see how it makes space usage any easier to reason about and can see how it makes it harder.  By using combinators you only have to know the properties of the combinator to know how it behaves, whereas I have to reanalyze each explicitly implemented function.  StackOverflow gives a good example of this for stack usage and folds.  As far as being "faster" I have no idea what the basis for that is; most likely GHC would inline into the recursive version anyways, and using higher-order list combinators makes deforesting easier.  At any rate, if using combinators makes it easier to correctly implement the function, then that should be the overriding concern.

-- DerekElkins

----
I read lots of code with recursion -- and it was hard to read, because it is hard to retrieve the data flow from it. -- HenningThielemann

----
IMO explicit recursion usually ''does'' make code harder to read, as it's trying to do two things at once: Recursing and performing the actual work it's supposed to do. Phrases like OnceAndOnlyOnce and SeparationOfConcerns come to the mind.
However, the concern about efficiency is (partly) justified. HOFs defined for certain recursion patterns often need additional care to achieve the same performance as functions using explicit recursion. As an example, in the following code, two sum functions are defined using two equivalent left folds, but only one of the folds is exported. Due to various peculiarities of GHCs strictness analyzer, simplifier etc, the call from main to mysum_2 works, yet the call to mysum_1 fails with a stack-overflow.
<haskell>
module Foo (myfoldl_1, mysum_1, mysum_2) where

-- exported
myfoldl_1 f z xs = fold z xs
    where
        fold z []       = z
        fold z (x:xs)   = fold (f z x) xs

-- not exported
myfoldl_2 f z xs = fold z xs
    where
        fold z []       = z
        fold z (x:xs)   = fold (f z x) xs

mysum_1 = myfoldl_1 (+) 0
mysum_2 = myfoldl_2 (+) 0
</haskell>
<haskell>
module Main where

import Foo

xs = [1..1000*1000]

main = do
    print (mysum_2 xs)
    print (mysum_1 xs)
</haskell>
(Results might differ for your particular GHC version, of course...)
-- RemiTurk

GHC made "broken" code work.  As covered in StackOverflow, foldl is simply not tail-recursive in a non-strict language.  Writing out mysum would still be broken.  The problem here isn't the use of a HOF, but simply the use of non-tail-recursive function.  The only "care" needed here is not relying on compiler optimizations (the code doesn't work in my version of GHC) or the care needed when relying on compiler optimizations.  Heck, the potential failure of inlining (and subsequent optimizations following from it) could be handled by restating recursion combinator definitions in each module that uses them; this would still be better than explicit recursion which essentially restates the definition for each expression that uses it.

-- DerekElkins

Here is a demonstration of the problem - with the classic sum as the problem.
Of course microbenchmarking has little sense, but it tells
us a little bit which combinator should be used.

<haskell>
import Data.List
import System

sum' :: Int -> Int -> Int

sum' 0 n = sum [1..n]
sum' 1 n = foldl (\a e -> a+e) 0 [1..n]
sum' 2 n = foldl (\a e -> let v = a+e in v `seq` v) 0 [1..n]
sum' 3 n = foldr (\a e -> a+e) 0 [1..n]
sum' 4 n = foldr (\a e -> let v = a+e in v `seq` v) 0 [1..n]
sum' 5 n = foldl' (\a e -> a+e) 0 [1..n]
sum' 6 n = foldl' (\a e -> let v = a+e in v `seq` v) 0 [1..n]
sum' 7 n = loop n 0
    where loop 0 acc = acc
          loop n acc = loop (n-1) (n+acc)
sum' 8 n = loop n 0
    where loop 0 acc = acc
          loop n acc = loop (n-1) $! n+acc


main = do [v,n] <- getArgs
          print $ sum' (read v) (read n)
</haskell>

When executing with n = 1000000 it produces the following results:
 * seq does not affect performance - as excepted.
 * foldr overflows stack - as excepted.
 * explicit loop takes 0.006s
 * foldl takes 0.040s
 * foldl' takes 0.080s

In this case the "correct" choice would be foldl' - ten times slower than explicit recursion.
This is not to say that using a fold would not be better for most code. Just that it can
have subtle evil effects in inner loops.

-- EinarKarttunen

This is ridiculous.  The "explicit recursion" version is not the explicit recursion version of the foldl' version.  Here is another set of programs and the results I get:
<haskell>
import Data.List
import System

paraNat :: (Int -> a -> a) -> a -> Int -> a
paraNat s = fold
    where fold z 0 = z
          fold z n = (fold $! s n z) (n-1)

localFoldl' c = fold
    where fold n [] = n
          fold n (x:xs) = (fold $! c n x) xs

sumFoldl' :: Int -> Int
sumFoldl' n = foldl' (+) 0 [1..n]

sumLocalFoldl' :: Int -> Int
sumLocalFoldl' n = localFoldl' (+) 0 [1..n]

sumParaNat :: Int -> Int
sumParaNat n = paraNat (+) 0 n

sumRecursionNat :: Int -> Int
sumRecursionNat n = loop n 0
    where loop 0 acc = acc
          loop n acc = loop (n-1) $! n+acc

sumRecursionList :: Int -> Int
sumRecursionList n = loop [1..n] 0
    where loop [] acc = acc
          loop (n:ns) acc = loop ns $! n+acc

main = do
    [v,n] <- getArgs
    case v of
        "1" -> print (sumFoldl' (read n))
        "2" -> print (sumLocalFoldl' (read n))
        "3" -> print (sumParaNat (read n))
        "4" -> print (sumRecursionNat (read n))
        "5" -> print (sumRecursionList (read n))
</haskell>

(best but typical real times according to time of a few trials each)
<haskell>
sumFoldl' takes 2.872s
sumLocalFoldl' takes 1.683s
sumParaNat takes 0.212s
sumRecursionNat takes 0.213s
sumRecursionList takes 1.669s
</haskell>

sumLocalFoldl' and sumRecursionList were practically identical in performance and sumParaNat and sumRecursionNat were practically identical in performance.  All that's demonstrated is the cost of detouring through lists (and the cost of module boundaries I guess).

-- DerekElkins