CS61ANotes – Week13 – Iterators,Generators,andStreamsIterators
Aniteratorisanabstractobjectthatrepresentsasequenceofvalues.Aniteratorunderstands
howtodotwothings.Firstofall,itknowshowtocalculateitsnextvalue,andhencecan
continuouslyoutputastreamofitsvalues.Secondly,aniteratorshouldknowwhenithasno
morevalueslefttocompute.WecanseethesetwobehaviorsbeingexhibitedinPython’s
iteratorinterface.Python’siteratorinterfaceusesa__next__methodthatcomputesthenext
valueinthesequencegiventheiterator’scurrentstate.Callingnext(<some-iterator>)willimplicitlycallthe__next__method,causingtheiteratortoreturnitsnextvalue.Whentherearenomorevalueslefttocompute,the__next__methodisrequiredtoraiseaStopIterationException,thussignalingtheendofthevaluesequence.
The__iter__methodisanothermethodusedinPython’siteratorinterface,anditmerely
returnstheiteratorobjectitself.Inotherwords,calling__iter__returnsanobjectthat
implementsthe__next__method.
Keepinmindthatiteratorsarestatefulobjectsandalwayskeeptrackofhowmuchofthe
streamhasalreadybeencomputed.Onceaniteratorinvokesits__next__method,the
calculatedvaluegets “used-up” andthrownaway,hencechangingtheiterator’sstate.Ifwe
thenmakeanothercallto__next__,thereturnedvaluewillbedifferentfromthepreviously
calculatedvalue.
HereisanexampleofaclassthatimplementsPython’siteratorinterface.Thisiterator
calculatesallofthenaturalnumbersone-by-one,startingfromzero:
classNaturals():
def__init__(self):
self.current=0
def__next__(self):
result=self.current
self.current+=1
returnresult
def__iter__(self):
returnself
Noticethatthe__next__methodinNaturalsneverraisesaStopIterationexception.Wait,but
IthoughtiteratorshavetoraiseaStopIterationexceptionwhentheycomputealloftheir
values!Exactly,butitdoesn’tmakesenseto “computethelastnaturalnumber”,asthesetof
naturalnumbersisinfinitelylarge.Hence,weseeherethatiteratorsareperfectlycapableof
representinganinfinitedatastreamusingafiniteamountofmemory.Alsonotethatbecausethereturnstatementmustbethelastoneexecutedinthe__next__method,wehavetosavethereturnvalueinatemporaryvariable,orelseitwouldgetoverwrittenbytheinterveningupdatestep.Lateronwewillintroducepython’syieldstatement,whichletsyoudefineiteratorsmorenaturally.
Questions
1.Defineaniteratorwhosei-thelementistheresultofcombiningthei-thelementsoftwoinputstreamsusingsomebinaryoperator,alsogivenasinput.Theresultingiteratorshouldhaveasizeequaltothesizeoftheshorterofitstwoinputiterators.
fromoperatorimportadd
evens=Iter_Combiner(Naturals(),Naturals(),add)
next(evens)
0
next(evens)
2
next(evens)
4
classIter_Combiner():
def__init__(self,iter1,iter2,combiner):
def__next__(self):
def__iter__(self):
returnself
2.Whatresultsfromexecutingthissequenceofcommands?
naturals=Naturals()
doubled_naturals=Iter_Combiner(naturals,naturals,add)
next(doubled_naturals)
______
next(doubled_naturals)
______
3.CreateaniteratorthatgeneratesthesequenceofFibonaccinumbers.
classFibonacci_Numbers():
def__init__(self):
def__next__(self):
def__iter__(self):
returnself
Generators
AgeneratorisaspecialkindofPythoniteratorthatusesayieldstatementinsteadofareturn
statementtoreportvalues.Ayieldstatementissimilartoareturnstatement,butwhereasa
returnstatementcausesthecurrentenvironmenttobedestroyedafterafunctionexits,ayield
statementinsideafunctioncausestheenvironmenttobesaveduntilthenexttime__next__
iscalled,whichallowsthegeneratortoautomaticallykeeptrackoftheiterationstate.Once__next__iscalledagain,executionpicksupfromwherethepreviouslyexecutedyieldstatementleftoff,andcontinuesuntilthenextyieldstatement(ortheendofthefunction)isencountered.IncludingayieldstatementinafunctionautomaticallysignalstoPythonthatthisfunctionwillcreateagenerator.Inotherwords,whenwecallthefunction,itwillreturnageneratorobject,insteadofexecutingthecodeinsidethebody.Whenthereturnedgenerator’s__next__methodiscalled,thecodeinthebodyisexecutedforthefirsttime,andstopsexecutinguponreachingthefirstyieldstatement.
Apythonfunctioncaneitherusereturnstatementsoryieldstatementsinthebodytooutput
values,butnotboth.Ifthefunctionhasasingleyieldstatement,thenpythontreatsthe
functionasagenerator,andwillraiseanerrorifthebodyalsocontainsareturnexpression
thatoutputsavalue.
Hereisaniteratorforthenaturalnumberswrittenusingthegeneratorconstruct:
defgenerate_naturals():
current=0
whileTrue:
yieldcurrent
current+=1
Questions
1.Inthisproblemwewillrepresentasetusingapythonlist.Writeageneratorfunctionthat
returnslistsofallsubsetsofthepositiveintegersfrom1ton.Eachcalltothisgenerator’s
__next__methodwillreturnalistofsubsetsoftheset[1,2, …,n],wherenisthenumberof
times__next__waspreviouslycalled.
subsets=generate_subsets()
next(subsets)
[[]]
next(subsets)
[[],[1]]
next(subsets)
[[],[1],[2],[1,2]]
defgenerate_subsets():
2.Defineageneratorthatyieldsthesequenceofperfectsquares.
defperfect_squares():
3.Rememberthehailstonesequencefromhomework1?Implementitusingagenerator!Togenerateahailstonesequence:
Pickapositivenumbern
Ifniseven,divideitby2
Ifnisodd,multiplyitby3andadd1
Continuethisprocessuntilnis1
defgenerate_hailstone(n=10):
Streams
Astreamisourthirdexampleofalazysequence.Astreamisalazilyevaluatedrlist.Inotherwords,thestream'selements(exceptforthefirstelement)areonlyevaluatedwhenthevaluesareneeded.Hence,aswithiteratorsandgenerators,streamscanbeusedtorepresentaninfiniteamountofdatawithoutusinganinfiniteamountofmemory.
Takealookatthefollowingcodefromlecture:
classStream(object):
def__init__(self,first,compute_rest,empty=False):
self.first=first
self._compute_rest=compute_rest
self.empty=empty
self._rest=None
self._computed=False
@property
defrest(self):
assertnotself.empty,'Emptystreamshavenorest.'
ifnotself._computed:
self._rest=self._compute_rest()
self._computed=True
returnself._rest
empty_stream=Stream(None,None,True)
WerepresentStreamsusingPythonobjects,similartothewaywedefinedrlists.Weneststreamsinsideoneanother,andcomputeoneelementofthesequenceatatime.Notethatinsteadofspecifyingalloftheelementsin__init__,weprovideafunction,compute_rest,thatencapsulatesthealgorithmusedtocalculatetheremainingelementsofthestream.Rememberthatthecodeinthefunctionbodyisnotevaluateduntilitiscalled,whichletsusimplementthedesiredevaluationbehavior.Thisimplementationofstreamsalsousesmemoization.Thefirsttimeaprogramasksastreamforitsrestfield,thestreamcodecomputestherequiredvalueusingcompute_rest,savestheresultingvalue,andthenreturnsit.Afterthat,everytimetherestfieldisreferenced,thestoredvalueissimplyreturnedand itisnotcomputedagain.
HereisanExample:
defmake_integer_stream(first=1):
defcompute_rest():
returnmake_integer_stream(first+1)
returnStream(first,compute_rest)
Noticewhatishappeninghere.Westartoutwithastreamwhosefirstelementis1,and
whosecompute_restfunctioncreatesanotherstream.Sowhenwedocomputetherest,we
getanotherstreamwhosefirstelementisonegreaterthanthepreviouselement,andwhosecompute_restcreatesanotherstream.Henceweeffectivelygetaninfinitestreamofintegers,computedoneatatime.Thisisalmostlikeaninfiniterecursion,butonewhichcanbeviewedonestepatatime,andsodoesnotcrash.
Questions:
1.WhatmodificationtotheStreamclasscouldbemadetoallowustodefineaninfinitestreamofrandomnumbers?
3.Writeaproceduremake_fib_stream()thatcreatesaninfinitestreamofFibonacci
Numbers.Makethefirsttwoelementsofthestream0and1.
Hint:Considerusingahelperprocedurethatcantaketwoarguments,thenthinkabout
howtostartcallingthatprocedure.
defmake_fib_stream()
2.Writeaproceduresub_streamsthattakesintwostreamsasargument,andreturns
theStreamofcorrespondingelementsfromthesecondstreamsubtractedfromthefirststream.YoucanassumethatbothStreamsareinfinite.
defsub_streams(stream1,stream2):
4.DefineaprocedurethatinputsaninfiniteStream,s,andatargetvalueandreturnsTrueifthestreamconvergestothetargetwithinacertainnumberofvalues.Forthisexamplewewillsaythestreamconvergesifthedifferencebetweentwoconsecutivevaluesandthedifferencebetweenthevalueandthetargetdropbelowmax_difffor10consecutivevalues.(Hint:createthestreamofdifferencesbetweenconsecutiveelementsusingsub_streams)
defconverges_to(s,target,max_diff=0.00001,num_values=100):
HigherOrderFunctionsonStreams:
Naturally,asthethemehasalwaysbeeninthisclass,wecanabstractourstreamprocedures
tobehigherorder.Takealookatfilter_streamfromlecture:
deffilter_stream(filter_func,stream):
defmake_filtered_rest():
returnfilter_stream(filter_func,stream.rest)
ifstream.empty:
returnstream
eliffilter_func(stream.first):
returnStream(s.first,make_filtered_rest)
else:
returnfilter_stream(filter_funct,stream.rest)
Youcanseehowthisfunctionmightbeuseful.NoticehowtheStreamwecreatehasasits
compute_restfunctionaprocedurethat “promises” tofilterouttherestoftheStreamwhen
asked.Soatanyonepoint,theentirestreamhasnotbeenfiltered.Instead,onlythepartof
thestreamthathasbeenreferencedhasbeenfiltered,buttherestwillbefilteredwhen
asked.WecanmodelotherhigherorderStreamproceduresafterthisone,andwecan
combineourhigherorderStreamprocedurestodoincrediblethings!
Questions:
1.Inasimilarmodeltofilter_stream,writeaproceduremap_stream,thattakesina
one-argumentfunction,anddoestheobviousthing.
defstream_map(func,stream):
2.ThefollowingprocedurewhencalledcreatesaStream.Givenendlesssubsequent
callstotheStreamtocomputeallitsvalues,whatarethevaluesoftheStreamcreated
bythecalltomy_stream().Don’twritethemall,justwriteenoughtogetthepattern.
defmy_stream():
defcompute_rest():
returnadd_streams(map_stream(double,my_stream()),my_stream())
returnStream(1,compute_rest)