[Haskell-cafe] Re: Josephus problem and style

[apfelmus]

Malcolm Wallace wrote:
> Anthony Chaumas-Pellet <achaumas at wispery.info> wrote:
>> Why is tail recursion a bad thing for a finite function?
>> Is tail recursion simply not the most common Haskell idiom, or is
>> there some technical reason I fail to see?
> 
> Tail recursion tends to create space-leaks, which in turn hurt time
> performance.

That's only part of the truth. Take for example the ordinary version of

   and :: (a -> Bool) -> [a] -> Bool

   and p []        = False
   and p (x:xs)    = p x && and xs

and it's tail-recursive cousin

   and' p []     b = b
   and' p (x:xs) b = and' p xs (b && p x)

Apparently, the function is True if there is some element in the list
that fulfills the condition p. Clearly, we can stop traversing the list
when we find the first element that satisfies p. Now, the tail-recursive
version is doomed to traverse the entire list, but thanks to lazy
evaluation, the ordinary version stops as soon as an element x with p x
is found.

Of course, one could alter the definition of and' to achieve early stopping

   and' _ _      True  = True
   and' p (x:xs) False = and' p xs (p x)
   and' _ []     False = False

but this is not advisable: we unfolded the definition of (&&). In the
ordinary case however, (&&) already contains all the magic of early
stopping, the recursion scheme has nothing to do with it.

Thus, the most common Haskell idiom about tail recursion is to not think
about it (and hence not use it). Instead, return values as early as
possible (in some cases (&&) can return a definite answer by looking at
the first argument only). Note that this is very different from strict
functional languages.

Regards,
apfelmus