Are these premises about folds and recursion right?

Question

When using foldr, the recursion occours inside the function, so, when the given function doesn't strictly evaluate both sides, and can return based on the first one, foldr must be a good solution, because it will work on infinity lists

findInt :: Int -> [Int] -> Bool
findInt z [] = False
-- The recursion occours inside de given function
findInt z (x:xs) 
  | z == x = True
  | otherwise = findInt z xs

equivalent to:

findInt' :: Int -> [Int] -> Bool
findInt' z = foldr (\x r -> if z == x then True else r) False
-- Where False is the "default value" (when it finds [], ex: findInt z [] = False)

A situation when foldr is not appropriate:

addAll :: Int -> [Int] -> Int
addAll z [] = z
-- The recursion occours outside the given function (+)
addAll z (x:xs) = addAll (z + x) xs

In this case, because + is strict (needs to evaluate both sides to return) it would be greately useful if we applied it in some way which we could have a redex (reducible expression), to make it possible to avoid thunks and (when forced to run with previous evaluation, not lazy) in constant space and without pushing to much onto the stack (similar to the advantages of a for loop in imperative algorithms)

addAll' :: Int -> [Int] -> Int
addAll' z [] = z
addAll' z (x:xs) = let z' = z + x
                  in seq z' $ addAll' z' xs

equivalent to:

addAll'' :: Int -> [Int] -> Int
addAll'' z = foldl' (+) z

In this little case, using foldr (inside recursion) doesn't make sense because it wouldn't make redexes. It would be like this:

addAll''' :: Int -> [Int] -> Int
addAll''' z [] = z
addAll''' z (x:xs) = (+) x $ addAll''' z xs

The main objective of this question is first, know whether my premises are right or where they could be better and second, help to make it more clear for others who are also learning Haskell the differences between inside and outside recursion, among the approaches, to have it clear in mind which one could be more appropriated to a given situation

Helpful links:

Haskell Wiki

Stackoverflow - Implications of foldr vs. foldl (or foldl')

I believe there is already more than one question about `foldl` vs `foldr` vs `foldl'` etc. and I believe they probably already answer everything you are asking. Try to search for them on SO and eventually, if they aren't satisfying, please link to them and state clearly what do they miss. — Bakuriu, Jul 09 '15 at 12:15
Thank you @Bakuriu for you suggestion, in my opinion, what they miss (which for me makes it clearer to understand), is the equivalence between the folds and the longer version functions, because it makes easier to see the patterns — FtheBuilder, Jul 09 '15 at 12:20
I suggest that you define `inside recursion` and `outside recursion` more explicitly to receive a high quality answer — recursion.ninja, Jul 09 '15 at 20:18
Late note (I had seen this question a while ago but forgot to comment): If I understood you well, a technical term for what you called "outside recursion" is "tail recursive", though by now you likely have figured it out on your own. FWIW, a link to another highly-relevant question: [foldl is tail recursive, so how come foldr runs faster than foldl?](http://stackoverflow.com/questions/3429634/foldl-is-tail-recursive-so-how-come-foldr-runs-faster-than-foldl) — duplode, Jul 22 '15 at 02:52

fgv · Accepted Answer · 2015-07-10T08:18:40.010

Aside from the fact that foldr is the natural catamorphism of a list, while foldl and foldl' are not, a few guidelines for their use:

you are correct on that foldr will always return, even on infinite lists, as long as the function is non-strict in its second argument, since the elements of the list are made available to the first argument of the function immediately (as opposed to foldl and foldl', where the elements of the list are not available to the first argument of the function until the list has been entirely consumed);
foldl' will be a better choice for non-infinite lists if you want to ensure constant space, since it's tail recursive, but it will always parse the entire list regardless of the strictness in the evaluation of the arguments to the function passed to it;
in general, foldr is equivalent to recursion, while foldl and foldl' are analogous to loops;
because of the fact that foldr is the natural catamorphism, if your function needs to recreate the list (for example, if your function is just the list constructor ':'), foldr would be more adequate;
with respect to foldl vs. foldl', foldl' is usually preferable because it will not build a huge thunk but, if the function passed to it is non strict in its first argument and the list is not infinite, foldl may return while foldl' may give an error (there is a good example in the Haskell wiki).

As a side note, I believe that you are using the term "inside recursion" to define foldr and "outside recursion" for foldl and foldl', but I haven't seen these terms before in the literature. More commonly these functions are just referred to as folding from the right and folding from the left respectively, terms that while may not be exactly correct, they give a good notion of the order in which the elements of the list are passed to the function.

I used **inside** and **outside** mainly because it is easier for me to imagine whether the recursive calls will happen inside (passed as argument to the given function), or the result of the given function will be used inside the recursion (outside) - Thank you for pointing out that _it's not in the standart literature_ and for giving us more explanations about the whole subject. — FtheBuilder, Jul 10 '15 at 16:23

Are these premises about folds and recursion right?

1 Answers1