On Mon, 19 Feb 2001, Christoph Rippel wrote:

> I just wanted to point out that besides its beauty this implementation
> is unfortunately much slower (maybe fifty times - fib is not a good 
> example since it has exponential behavior, so the arithmetic becomes 
> the dominating factor for ``moderately large n'') then a more down 
> to earth implementation like

Despite a regular functional implementation of fib(n) being in O(fib(n)) 
time (that is, O(1.618**n) time), the implementation with generators is in
O(n) time like yours [*]. The only difference is callcc (which I think is
quite slow, but I don't know how it's implemented).

I don't see how fib wouldn't be a good example. The existence of an
O(fib(n)) solution is irrelevant. You can design a slow solution to every
problem possible.



matju

[*] actually that's for small numbers. For large ones, it's O(n log n).
The other one is similarly slower but it doesn't matter because no-one
can run that on big numbers.