Comment by spockz

5 years ago

If you like tail calls, look into CPS. Many forms of (pure) code can be rewritten in such a way.

Everyone who writes Haskell quickly learns to write their recursive functions so that they are (mutually) tail recursive.

2 comments

spockz

dwohnitmok 5 years ago

It's a bit of a weird case for Haskell. Because of laziness, you don't always want tail recursion (in fact sometimes you definitely don't want the tail recursive version). The classic example of this is foldl vs foldr.

  -- Tail-recursive so must be good right?
  -- That way lies thunk accumulation and *non-constant* 
  -- additional memory usage for a lot of functions f
  foldl f acc []     = acc
  foldl f acc (x:xs) = foldl f (f acc x) xs

  -- In contrast, this definition often results in constant 
  -- additional space usage despite the non-tail call.
  foldr f acc []     = acc
  foldr f acc (x:xs) = f x (foldr f acc xs)

Tail recursion is an unalloyed good only for strict languages.

Although I'm not sure why you put mutual in parentheses and maybe you meant to address laziness with that?

spockz 5 years ago

You are right indeed regarding that there are cases where trail recursion does not work. But in this case I would say that the culprit is the laziness of f.
I put mutual in between parentheses because not all languages support optimising mutually tail recursive functions.