> Actually calculating the Fibonacci series efficiently in a non-lazy functional language looks surprisingly non-trivial.

I don't know if you'd count it as trivial, but one could do

    def fib(n, a=0, b=1, c=2):
        if n <= 1:
            return n
        if n == c:
            return a+b
        return fib(n, b, a+b, c+1)

which beats the Haskell lazy list in being O(1) space (except Python doesn't eliminate tail calls).