Loading ...
Sorry, an error occurred while loading the content.

Re: [python-iter] Iteration and dynamic programming

Expand Messages
  • qrczak@knm.org.pl
    ... IMHO the right abstraction here is a lazy list, not an iterator. It can be done and packed in a useful module, although the syntax of building lazy lists
    Message 1 of 6 , Mar 13, 2001
    • 0 Attachment
      Tue, 13 Mar 2001 19:05:03 +0100, Magnus Lie Hetland <mlh@...> pisze:

      > I just started thinking about a Fibonacci iterator.
      > And then I started to generalise a bit.

      IMHO the right abstraction here is a lazy list, not an iterator.
      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,
      fibs,
      fibs[1:])))

      It really benefits from garbage collection able to reclaim cycles
      and nested scopes.

      --
      __("< Marcin Kowalczyk * qrczak@... http://qrczak.ids.net.pl/
      \__/
      ^^ SYGNATURA ZAST─śPCZA
      QRCZAK
    Your message has been successfully submitted and would be delivered to recipients shortly.