I am studying a bit of functional programming using haskell and I am trying to go through some concepts by re-implementing some library functions.
I have a question though mainly in regards to when it is better to choose recursion over iteration. For example when reimplementing the "all" function I can choose between:
all1 :: (a -> Bool) -> [a] -> Bool
all1 p xs = foldr (\x acc -> acc && p x) True xs
all2 :: (a -> Bool) -> [a] -> Bool
all2 p (x:xs)
| p x == False = False
| otherwise = all2 p xs
The way I look at it, the recursive one should be more time efficient since it will stop at the first non-matching entry, while the folding one is more space efficient (I think, still not clear about tail recursion optimisation in haskell) but it will always scan the full list, unless there is some clever optimisation done by looking at the fact that false will always give false once it's there.
So, is this compromise something which is always there? Am I misunderstanding something in the way recursion and folding work?
Let's consider, brick by brick, whether a foldr-based solution can short-circuit. To begin with, (&&) is defined like this:
(&&) :: Bool -> Bool -> Bool
True && x = x
False && _ = False
Given the second clause, and thanks to laziness, the second argument to (&&) is ignored if the first one is False -- in other words, it short-circuits.
Next, this is foldr for lists:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr k z = go
where
go [] = z
go (y:ys) = y `k` go ys
If y `k` go ys can be evaluated without looking at go ys, there will be no recursive call, and the fold as a whole will shortcut.
In all1, the binary operation is \x acc -> acc && p x. That isn't good enough for our purposes, for passing acc (which corresponds the go ys in the foldr definition) as the first, short-circuiting, argument of (&&) leads to the whole list being consumed regardless of what p x turns out to be. Not all is lost, though: swapping the arguments to (&&)...
all3 :: (a -> Bool) -> [a] -> Bool
all3 p xs = foldr (\x acc -> p x && acc) True xs
... gives us the desired short-circuiting.