Here is a question for people who are more comfortable than
I am with new Python stuff like generators.
I am having fun implementing things from the Wizard book
(Abelson, Sussman, "Structure and Interpretation of Computer
Programs") in Python. In chapter 3.5 it is about streams as
delayed lists.
Streams are interesting because they are to lists like
xrange is to range. Could save a lot on memory and
computations.
Below is my straight translation from Scheme code in the
Wizard book to Python. It works, but now I want to rewrite
the delay and force functions using Python's new stuff,
generators or iterators or what-have-you. I have the
feeling that that is possible, can you do it?
The program below creates a stream with the numbers 1..995
and then filters the stream, keeping only the even numbers,
and then prints the second number in the stream (implemented
as the first number of the tail, just like in the 3.5
Section in the Wizard book).
.. # file: teststreams.py
..
.. def delay(exp): return lambda: exp
..
.. def force(o): return o()
..
.. def cons_stream(a,b ): return [a, delay(b)]
..
.. def stream_hd(s): return s[0]
..
.. # we use tl for cdr
.. def tl(x):
.. if len(x) == 2: return x[1]
.. else: return x[1:]
..
.. def stream_tl(s): return force(tl(s))
..
.. def stream_enumerat e_interval(low, high):
.. if low > high:
.. return None
.. else:
.. return cons_stream(
.. low,
.. stream_enumerat e_interval(low+ 1, high))
..
.. def stream_filter(p red, s):
.. if s is None:
.. return None
.. elif pred(stream_hd( s)):
.. return cons_stream(
.. stream_hd(s),
.. stream_filter(p red, stream_tl(s)))
.. else:
.. return stream_filter(p red, stream_tl(s))
..
.. def isEven(n): return n % 2 == 0
..
.. print stream_hd(strea m_tl(stream_fil ter(
.. isEven,
.. stream_enumerat e_interval(1,99 5))))
.. # 4
Something else: this crashes with a "maximum recursion reached"
.. print stream_enumerat e_interval(1,99 8)
while this does not crash
.. print stream_enumerat e_interval(1,90 0)
this means Python has a maximum of something like 900
recursions?
Jul 18 '05
17 2478
Just for the record, an implementation without using generators,
somewhat like in Sect. 3.5 of the Wizard book, and without recursion
limit problems.
..
.. def stream_hd(s): # the head of the stream
.. return s[0]
..
.. def stream_tl(s): # the tail of the stream
.. return s[1]()
..
.. ##
.. # The low argument is required: the first element of the stream.
.. # You either use high= or stop_f= to define the end of the
.. # stream. Omit both for an infinite stream. stop_f is a function
.. # that takes low as argument and returns True or False.
.. # The next_f function takes one argument (an element of the stream,
.. # same type as the low argument has)
.. # The stop_f function takes one argument (same type as low)
.. # @param low object
.. # @param high object
.. # @param next_f function
.. # @param stop_f function
.. # @return list, a stream
.. def make_stream(low , high=None, next_f=None, stop_f=None):
.. if next_f is None: next_f = lambda x: x + 1
.. if high is not None: # using high
.. if low > high:
.. return None
.. else:
.. return [low, lambda: make_stream(
.. next_f(low), high=high, next_f=next_f)]
.. elif stop_f is not None: # using stop_f
.. if low > stop_f(low):
.. return None
.. else:
.. return [low, lambda: make_stream(
.. next_f(low), next_f=next_f, stop_f=stop_f)]
.. else: # infinite stream
.. return [low, lambda: make_stream(
.. next_f(low), next_f=next_f)]
..
.. ##
.. # iterative version of filter
.. # @param pred function, (stream-element) -> bool
.. # @param s list, a stream
.. # @return list, a stream
.. def stream_filter(p red, s):
.. if s is None: return []
.. while True:
.. elem = stream_hd(s)
.. if pred(elem):
.. return [elem, lambda: stream_filter(p red, stream_tl(s))]
.. else:
.. s = stream_tl(s)
.. if s is None: return []
..
..
.. if __name__ == '__main__':
..
.. def is100some(x): return x % 100 == 0
.. assert(stream_h d(stream_tl(str eam_tl(stream_f ilter(
.. is100some,
.. make_stream(1, 11111111111111) )))) == 300)
..
.. def add_33(x): return x + 33
.. assert(stream_h d(stream_tl(str eam_filter(
.. is100some,
.. # stream 1,34,67,100,...
.. make_stream(1,9 99999999, next_f = add_33)))) == 3400)
..
.. assert(stream_h d(stream_tl(str eam_filter(
.. is100some,
.. # infinite stream 1,2,...
.. make_stream(1)) )) == 200)
..
.. def mod_20000(x): return x % 20000 == 0
.. # this will need more evaluations than the recursion limit count
.. infinite_filter = stream_filter(m od_20000, make_stream(1))
.. assert( stream_hd(strea m_tl(infinite_f ilter)) == 40000 )
..
Nick Coghlan wrote: Will Stuyvesant wrote:
The program below creates a stream with the numbers 1..995 and then filters the stream, keeping only the even numbers, and then prints the second number in the stream (implemented as the first number of the tail, just like in the 3.5 Section in the Wizard book).
How's this:
Py> from itertools import islice Py> print islice((x for x in xrange(1, 996) if x % 2 == 0), 1, 2).next() 4
Wouldn't it be nice if this could be spelt:
print (x for x in xrange(1, 996) if x % 2 == 0)[2]
Well, I just put a patch on SF to enable exactly that: http://www.python.org/sf/1108272
Cheers,
Nick.
--
Nick Coghlan | nc******@email. com | Brisbane, Australia
--------------------------------------------------------------- http://boredomandlaziness.skystorm.net
Nick Coghlan wrote: How's this:
Py> from itertools import islice Py> print islice((x for x in xrange(1, 996) if x % 2 == 0), 1, 2).next() 4
Wouldn't it be nice if this could be spelt:
print (x for x in xrange(1, 996) if x % 2 == 0)[2]
as I've always said, the sooner we can all use the itertools goodies without
even noticing, the better.
</F>
Nick Coghlan wrote: Py> print islice((x for x in xrange(1, 996) if x % 2 == 0), 1, 2).next() 4
Wouldn't it be nice if this could be spelt:
print (x for x in xrange(1, 996) if x % 2 == 0)[2]
Well, I just put a patch on SF to enable exactly that: http://www.python.org/sf/1108272
I like it. Of course you always have to bear in mind that one giant leap for
a list could be _many_ small steps for an iterator.
Peter
Peter Otten wrote: Nick Coghlan wrote:
Py> print islice((x for x in xrange(1, 996) if x % 2 == 0), 1, 2).next() 4
Wouldn't it be nice if this could be spelt:
print (x for x in xrange(1, 996) if x % 2 == 0)[2]
Well, I just put a patch on SF to enable exactly that: http://www.python.org/sf/1108272
I like it. Of course you always have to bear in mind that one giant leap for a list could be _many_ small steps for an iterator.
Indeed. The main cases I am thinking of involve picking off the first few items
of an iterator (either to use them, or to throw them away before using the rest).
And if an app actually *needs* random access, there's a reason lists still exist ;)
Cheers,
Nick.
--
Nick Coghlan | nc******@email. com | Brisbane, Australia
--------------------------------------------------------------- http://boredomandlaziness.skystorm.net
Nick Coghlan <nc******@iinet .net.au> writes:
[...] (xrange can't handle Python longs, unfortunately, so we *are* constrained by sys.maxint. However, since my machine only has half a gig of RAM, the above is still a damn sight quicker than the equivalent list comprehension would be!)
[...]
Other way 'round: if you had even more RAM, the listcomp would be even
slower for this job!
John
On Tue, 25 Jan 2005 23:53:26 +1000, Nick Coghlan <nc******@iinet .net.au> wrote: Peter Otten wrote: Nick Coghlan wrote:
Py> print islice((x for x in xrange(1, 996) if x % 2 == 0), 1, 2).next() 4
Wouldn't it be nice if this could be spelt:
print (x for x in xrange(1, 996) if x % 2 == 0)[2]
Well, I just put a patch on SF to enable exactly that: http://www.python.org/sf/1108272
I like it. Of course you always have to bear in mind that one giant leap for a list could be _many_ small steps for an iterator.
Indeed. The main cases I am thinking of involve picking off the first few items of an iterator (either to use them, or to throw them away before using the rest).
And if an app actually *needs* random access, there's a reason lists still exist ;)
You can bail out of a generator expression with a raise-StopIteration expression spelled iter([]).next() ;-) def show(x): print x,; return x
... list(show(x) for x in xrange(20) if x<8 or iter([]).next())
0 1 2 3 4 5 6 7
[0, 1, 2, 3, 4, 5, 6, 7]
Well, since
list(show(x) for x in xrange(20) if x<8)
0 1 2 3 4 5 6 7
[0, 1, 2, 3, 4, 5, 6, 7]
this change due to adding iter([]).next() might be more convincing:
list(show(x) for x in xrange(20) if x<8 or True)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
list(show(x) for x in xrange(20) if x<8 or iter([]).next() or True)
0 1 2 3 4 5 6 7
[0, 1, 2, 3, 4, 5, 6, 7]
Applied to example,
print list(x for i,x in enumerate(x for x in xrange(1, 996) if x % 2 ==0) if i<3 or iter([]).next())[2]
6
or in case you just want one item as result,
print list(x for i,x in enumerate(x for x in xrange(1, 996) if x % 2 ==0) if i==2 or i==3 and iter([]).next())[0]
6
Regards,
Bengt Richter
Bengt Richter wrote: You can bail out of a generator expression with a raise-StopIteration expression spelled iter([]).next() ;-)
>>> list(show(x) for x in xrange(20) if x<8 or iter([]).next() or True)
0 1 2 3 4 5 6 7 [0, 1, 2, 3, 4, 5, 6, 7]
This is both neat and incredibly arcane at the same time :)
Cheers,
Nick.
--
Nick Coghlan | nc******@email. com | Brisbane, Australia
--------------------------------------------------------------- http://boredomandlaziness.skystorm.net This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Conrad |
last post by:
Greetings,
Q: Is there some way to gracefully suspend a python app for a second or
so then resume? I could write the classic basic dumb
loop-tenzillion-times delay, but that seems inelegant, and well, just
wrong. By the way, I'm also using wxPython, if that helps any.
I need to delay a python program for about a second. Googling around, it
looks like most of the timer stuff has to do with thread handling, but my
application is not...
|
by: jacob c. |
last post by:
When I request a URL using urllib2, it appears that urllib2 always
makes the request using HTTP 1.0, and not HTTP 1.1. I'm trying to use
the "If-None-Match"/"ETag" HTTP headers to conserve bandwidth, but if
I'm not mistaken, these are HTTP 1.1 headers, so I can't reasonably
expect a web server to respond correctly to my requests. (In my
limited testing, it looks like some servers respond correctly with an
HTTP 304 status, while some...
|
by: Doug Thews |
last post by:
I ran into an interesting re-pain delay after calling the Abort() method on
a thread, but it only happens the very first time I call it. Every time
afterward, there is no delay.
I've got a delegate inside the UI that I call to update the progress meter.
I use the Suspend() and Abort() methods based on button events.
I can watch the progress meter increase just fine when the thread is
running. When I select Start, I enable the Cancel...
|
by: mfeingold |
last post by:
I am working on a system, which among other things includes a server and a
..net control sitting in an html page and connected to the server. I ran into
a couple of problems, you guys might have some insight about.
1) It takes 20 sec or so to open a tcp socket from the client to the server.
It just sits in the TcpClient.conect waiting for something. When I run the
same control from a windows application it connects right away and works...
|
by: Martin |
last post by:
Using javascript, I want to force a browser window to close after
about 30 minutes of non-use. Can someone point me to a script that can
do this?
I assume I could use the setTimeout function and keep re-setting it
whenever the mouse is moved.
Is there a better way?
| |
by: ShawnD |
last post by:
I'm having some issues when trying to read input off of a pipe using a python script. I'm trying to process packet data from tcpdump in real-time, so it's a filter that needs to read data while the process being piped from is still reading.
On both my Linux and OSX system, it seems that there's a large delay reading from stdin if the process being read from is still running, even if it's producing output to be read. It will wait until it...
|
by: Jonathan Mark |
last post by:
hi all...
I wrote a seemingly simple function (below) to use Popen3() and select()
to run a program and capture its exit status, stdout output, and stderr
output.
It worked fine until the box was upgraded to Debian sarge.
Now the call to select() always takes about 13 seconds before returning
the first time.
The delay only occurs when the function is running within a CGI program
|
by: dwhall |
last post by:
I have 2 python scripts: examples of a producer and a filter,
respectively:
#! /usr/bin/env python
import sys, time
if __name__ == "__main__":
while True:
sys.stdout.write("hello.\r\n")
time.sleep(0.000001)
|
by: sheldonlg |
last post by:
I came across a problem and googling for an answer didn't help.
What I want to do is run an AJAX script that sets a hidden variable on
the form. I call the AJAX script from a javascript function. After the
call, I check the value of that hidden variable and proceed according to
whether it is zero or one.
The problem is that the AJAX call does not complete before the test.
So, I put in a delay after the call to the AJAX function. I...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
| |
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |