Re: [python-iter] Iteration and dynamic programming
- Tue, 13 Mar 2001 19:05:03 +0100, Magnus Lie Hetland <mlh@...> pisze:
> I just started thinking about a Fibonacci iterator.IMHO the right abstraction here is a lazy list, not an iterator.
> And then I started to generalise a bit.
It can be done and packed in a useful module, although the syntax
of building lazy lists will be somewhat ugly.
I'm sure I've seen a module which implements Haskell-like laziness.
A lazy list differs from a normal list in that its elements are
computed on demand. They are cached. It is quite compatible with
Python's sequence protocol, even though indexing by number is unusual
for what I got used to, and it would dictate a specific representation.
It is yet better compatible with the proposed iterator interface.
I.e. an iterator over a lazy list is easy and natural. In this
environment it can be represented as a traditional list, not as a
wrapped array, i.e. as a pair of the head (first element) and the
lazily computed tail (the rest of elements), unless it's empty.
The classic Fibonacci sequence definition in Haskell:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
This corresponds to the following in Python, assuming appropriate
definitions were made:
fibs = cons (0L, lambda:
cons (1L, lambda:
zip_with (lambda x, y: x + y,
It really benefits from garbage collection able to reclaim cycles
and nested scopes.
__("< Marcin Kowalczyk * qrczak@... http://qrczak.ids.net.pl/
^^ SYGNATURA ZASTĘPCZA