[Haskell-cafe] Optmiization of recursion

[Marcin 'Qrczak' Kowalczyk]

John Goerzen <jgoerzen at complete.org> writes:

> The OCaml compiler was able to optimize tail-recursive functions such
> that they could be compiled using a loop.  This would achieve two main
> benefits: performance due to not needing to allocate/deallocate stack
> frames, and the ability to work on very large lists since each recursive
> call did not consume extra stack space.
>
> So I have several questions about Haskell:
>
> 1. Do Haskell interpreters/compilers perform similar optimizations?

Yes.

> 3. Does it make a difference for optimization purposes whether a
> particular recursive function is tail-recursive?

Similarly to OCaml. Except that a non-tail-recursive function doesn't
necessarily use a large amount of stack, because of laziness. For
example map doesn't process the whole list at once; it immediately
returns a cons cell which, when its tail is evaluated, causes map
to proceed further.

> 4. Is a reference available documenting which Prelude/standard functions
> are properly tail-recursive (and thus suitable for very large lists) and
> which are not?

I don't think so. It should be safe to assume that functions have
time/space properties like their sources in the Haskell report,
but I'm not sure if there are exceptions.

But as I said, non-tail recursion is not necessarily a problem. Most
functions are suitable for large lists even if they are not tail
recursive; when they use O(N) memory, it's on the heap rather than
on the stack and it's unavoidable.

> (OCaml system docs generally specify when a function is not
> tail-recursive... for instance, one of foldr/foldl is and the other
> isn't.)

This is a tricky issue. In OCaml and similar languages foldl runs in
constant stack space, assuming the function given uses a constant
stack space, while foldr must traverse the whole list before it begins
any work and it uses O(N) stack space.

In Haskell foldr is efficient if the given function is lazy in its
second argument, or if it enters its second argument in *its* tail
position, and O(N) if it does something after evaluation of its second
argument. And it's mixed if the function behaves differently on
different times, depending on its first argument for example.

OTOH foldl is tail-recursive, but the loop only builds a thunk of size
O(N), which then uses O(N) of stack if the folded function does some
computation after entering its first argument, or better otherwise.
*But* if the compiler is able to inline it and statically determine
that the folded function is always strict (GHC usually does this but
other implementations don't), it can transform the code accordingly
such that it doesn't use O(N) stack.

Some implementations also provide foldl', which is a strict variant of
foldl: it artificially makes the folded function strict (by using seq)
and has this seq use inlined, so it will always be as efficient as
the folded function permits, but for weird functions it may evaluate
something that foldl would not evaluate at all. I wish foldl' was in
standard Haskell, because it's usually the same as foldl but doesn't
rely on sophisticated compiler optimizations to be efficient.

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak at knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/