Informatics1–FunctionalProgramming:Tutorial7
Heijltjes,Wadler
Due:Thetutorialofweek9(20/21Nov.)
Readingassignment:Chapters15–17(pp.280–382)
Pleaseattempttheentireworksheetinadvanceofthetutorial,andbringwithyouallwork,including(ifacomputerisinvolved)printoutsofcodeandtestresults.Tutorialscannotfunctionproperlyunlessyoudotheworkinadvance.
Youmayworkwithothers,butyoumustunderstandthework;youcan’tphoneafriendduringtheexam.
Assessmentisformative,meaningthatmarksfromcourseworkdonotcontributetothefinalmark.Butcourseworkisnotoptional.Ifyoudonotdothecourseworkyouareunlikelytopasstheexams.
Attendanceattutorialsisobligatory;pleaseletyourtutorknowifyoucannotattend.
Turtlegraphics
Turtlegraphicsisasimplewayofmakinglinedrawings.1Theturtlehasagivenlocationonthecanvasandisfacinginagivendirection.Acommanddescribesasequenceofactionstobeundertakenbyaturtle,includingmovingforwardagivendistanceorturningthroughagivenangle.TurtlecommandscanberepresentedinHaskellusinganalgebraicdatatype:
typeDistance=FloattypeAngle=Float
dataCommand=GoDistance
|TurnAngle|Sit
|Command:#:Command
ThelastlineusesHaskell’sfacilitytodeclareaninfixoperatorasaconstructorofanalgebraictype.Suchoperatorsmustalwaysbeginwithacolon,justasoperatornamesmustalwaysbeginwithanuppercaseletter.Inthiscase,weusetheoperator:#:tojointwocommands.Thus,acommandhasoneoffourforms:
•God,wheredisadistance—movetheturtlethegivendistanceinthedirectionitisfacing.(Note:distancesarenotexpectedtobenegative.)•Turna,whereaisanangle—turntheturtleanticlockwisethroughthegivenangle.
exerciseinbasedonasimilarexerciseusedatImperialCollege.
logo-foundation/logo/turtle.htmlformoreonturtlegraphics.
1This
Seehttp://el.media.mit.edu/
1
Turn 120Go 30Go 30Turn 120Go 30StartFigure1:Drawingatrianglewithturtlecommands
•Sit—donothing:leavestheturtle’spositionanddirectionunchanged.
•p:#:q,wherepandqarethemselvescommands—executethetwogivencommandsinsequence.Forinstance,todrawanequilateraltrianglewithsidesofthirtyunits,weneedtoordertheturtletomoveforwardthreetimes,turning120◦betweenmoves:
Go30:#:Turn120:#:Go30:#:Turn120:#:Go30(SeeFigure1.)
Viewingpaths
Youcanviewaturtle’spathbytyping
*Main>displaypath
wherepathisanexpressionoftypeCommand.Forexample,
*Main>display(Go30:#:Turn120:#:Go30:#:Turn120:#:Go30)drawsthetriangledescribedabove.
Equivalences
Notethat:#:isanassociativeoperatorwithidentitySit.Sowehave:
p:#:SitSit:#:p
p:#:(q:#:r)
===
pp
(p:#:q):#:r
2
Wecanomitparenthesesinexpressionswith:#:because,wherevertheyareplaced,themeaningremainsthesame.Inthisassignment,whenwesaythattwocommandsareequivalentwemeanthattheyarethesameaccordingtotheequalitieslistedabove.
However,toevaluateanexpressionHaskellhastoplaceparentheses;ifyouaskittoshowacommand,itwillalsoshowwhereithasplacedthem:
*Main>Sit:#:Sit:#:SitSit:#:(Sit:#:Sit)Exercises
1.Inthisfirstexercisewewillexploretheequivalenceofturtlecommandsandconvertthemintolistsandback.
(a)Writeafunction
split::Command->[Command]
thatconvertsacommandtoalistofindividualcommandscontainingno:#:orSitelements.Forexample,
*Main>split(Go3:#:Turn4:#:Go7)[Go3,Turn4,Go7]
Notethattwocommandsareequivalentifsplitreturnsthesameresultforboth.
*Main>[Go3,*Main>[Go3,
split((Go3:#:Turn4):#:(Sit:#:Go7))Turn4,Go7]
split(((Sit:#:Go3):#:Turn4):#:Go7)Turn4,Go7]
(b)Writeafunction
join::[Command]->Command
thatconvertsalistofcommandsintoasinglecommandbyjoiningtheelementstogether.Forexample,
*Main>join[Go3,Turn4,Go7]Go3:#:Turn4:#:Go7:#:Sit
Asinallourexamples,theresultcanbeanycommandequivalenttothegivencommand.(c)WriteaQuickCheckpropertythatteststhatsplit(join(splitc))isthesameas
splitc,wherecisanarbitrarycommand.2.Usingtheabovetranslationfromlists,wewillwriteafunctiontodrawregularpolygons.
(a)Writeafunction
copy::Int->Command->Command
whichgivenanintegerandacommandreturnsanewcommandconsistingofthegivennumberofcopiesofthegivencommand,joinedtogether.Thus,thefollowingtwocom-mandsshouldbeequivalent:
copy3(Go10:#:Turn120)
Go10:#:Turn120:#:Go10:#:Turn120:#:Go10:#:Turn120
(b)Usingcopy,writeafunction
pentagon::Distance->Command
3
thatreturnsacommandwhichtracesapentagonwithsidesofagivenlength.Thus,thefollowingtwocommandsshouldbeequivalent:pentagon50(Go50.0:#:Go50.0:#:Go50.0:#:Go50.0:#:Go50.0:#:(c)Writeafunction
polygon::Distance->Int->Command
thatreturnsacommandthatcausestheturtletotraceapathwiththegivennumberofsides,ofthespecifiedlength.Thus,thefollowingtwocommandsshouldbeequivalent:
polygon505pentagon50
Hint:YoumayneedtousethePreludefunctionfromIntegraltoconvertanInttoaFloat.
3.Next,wewillapproximateaspiral,bymakingourturtletravelincreasing(ordecreasing)lengthsandturningslightlyinbetween.Ourfunctioncopyisofnohelphere,sincethedistancetheturtletravelschangesaftereachcornerittakes.Therefore,yourspiralfunctionwillhavetoberecursive.It’stypesignatureshouldbeasfollows:
spiral::Distance->Int->Distance->Angle->CommandItsparametersare
•side,thelengthofthefirstsegment,•n,thenumberoflinesegmentstodraw,
•step,theamountbywhichthelengthofsuccessivesegmentschanges,and•angle,theangletoturnaftereachsegment.
Todrawsuchaspiral,wedrawnlinesegments,eachofwhichmakesangleanglewiththepreviousone;thefirstshouldbeaslongassegmentandthereaftereachoneshouldbelongerbystep(orshorter,ifstepisnegative).
Thus,thefollowingtwocommandsshouldbeequivalent:
spiral30(Go30.0Go35.0Go40.0Go45.0
45:#::#::#::#:
30TurnTurnTurnTurn
30.030.030.030.0
:#::#::#:)
TurnTurnTurnTurnTurn
72.072.072.072.072.0
:#::#::#::#:)
Note:yourrecursionshoulddefinitelystopafternsteps(thesecondparameter),butyouwillalsoneedtokeepinmindthatlinesegmentsshouldbetternotbecomenegativeinlength.SampleoutputisshowninFigure2.
4.(Optional)Besidestheequalitieswesawearlier,wemightalsowanttoconsiderthefollowingones:
Go0=Sit
God:#:Goe=Go(d+e)Turn0=Sit
Turna:#:Turnb=Turn(a+b)
4
Figure2:Spiral(fromspiral0.110000.14)
SotheSitcommandisequivalenttoeithermovingorturningbyzero,andanysequenceofconsecutivemovesorturnscanbecollapsedintoasinglemoveorturn.Writeafunction:
optimise::Command->Command
which,givenacommandp,returnsacommandqthatdrawsthesamepicture,butwiththefollowingproperties:
•qcontainsnoSit,Go0orTurn0commands.•qcontainsnoadjacentGocommands.•qcontainsnoadjacentTurncommands.Forexample:
*Main>optimise(Go10:#:Sit:#:Go20:#:
Turn35:#:Go0:#:Turn15:#:Turn(-50))
Go30.0
Note:Thisoneisfairlytricky.Youmayneedtokeeptryingoptimisationsuntilnoneofthemwork,butbewareofinfiniteloops!Think:Howwillyourecognizewhenyoucan’toptimiseanyfurther?
Branchingandcolours
Sofarwe’veonlybeenabletodrawlinearpaths;wehaven’tbeenabletobranchthepathinanyway.Inthenextsection,wewillmakeuseoftwoadditionalcommandconstructors:dataCommand=...
|GrabPenPen|BranchCommandwherePenisdefinedas:
5
dataPen=ColourFloatFloatFloat
|InklessThesegivetwoadditionalformsofpath.
•GrabPenp,wherepisapen:causestheturtletoswitchtoapenofthegivencolour.Thefollowingpensarepredefined:
white,black,red,green,blue::Pen
YoucancreatepenswithothercoloursusingtheColourconstructor,whichtakesavaluebetween0and1.0foreachofthered,greenandbluecomponentsofthecolour.ThespecialInklesspenmakesnooutput;youcanuseInklesstocreatedisjointpictureswithasinglecommand.
•Branchp,wherepisapath:drawsthegivenpathandthenreturnstheturtletodirectionandpositionwhichithadatthestartofthepath(ratherthanleavingitattheend).Penchangeswithinabranchhavenoeffectoutsidethebranch.Toseetheeffectofbranching,drawthefollowingpath.
letinDirectionangle=Branch(Turnangle:#:Go100)in
join(mapinDirection[20,40..360])
IntroductiontoL-Systems
TheSwedishbiologistAristidLindenmayerdevelopedL-Systemstomodelthedevelopmentofplants.2AnL-Systemconsistsofastartpatternandasetofrewriteruleswhicharerecursivelyappliedtothepatterntoproducefurtherincreasinglycomplexpatterns.Forexample,Figure3wasproducedfromthe“triangle”L-System:
angle:start:rewrite:
90+f
f→f+f-f-f+f
EachsymbolinthestringgeneratedbyanL-Systemrepresentsapathcommand:here,+and-representclockwiseandanticlockwiserotationandfrepresentsaforwardmovement.Whichsymbolsrepresentwhichcommandsisamatterofconvention.
Inthissystem,onlythesymbolfisrewritten,whilethe+and-symbolsarenot.Therewritingreplacesthestraightlineswithmorecomplexfigures.
HereishowtogenerateapicturewithanL-System.Beginwiththestartpattern.Thenapplytherewriterulesomenumberoftimes,replacingthecharacterontheleftbythesequenceontheright.Forinstance,applyingtheaboverulethreetimesgivesthefollowingstringsinsuccessivesteps:
moreonL-Systems,tryhttp://en.wikipedia.org/wiki/L-System.Averynicebook,TheAlgorith-micBeautyofPlants,containsbeautifulcolorillustrationsproducedbyL-Systems;itisavailableonlineathttp://algorithmicbotany.org/papers/#abop
2For
6
Figure3:TriangleL-Systemoutput
Step012
Pattern+f
+f+f-f-f+f
+f+f-f-f+f+f+f-f-f+f-f+f-f-f+f-f+f-f-f+f+f+f-f-f+f+f+f-f-f+f+f+f-f-f+f-f+f-f-f+f-f+f-f-f+f+f+f-f-f+f+f+f-f-f+f+f+f-f-f+f-f+f-f-f+f-f+f-f-f+f+f+f-f-f+f-f+f-f-f+f+f+f-f-f+f-f+f-f-f+f-f+f-f-f+f+f+f-f-f+f-f+f-f-f+f+f+f-f-f+f-f+f-f-f+f-f+f-f-f+f+f+f-f-f+f+f+f-f-f+f+f+f-f-f+f-f+f-f-f+f-f+f-f-f+f+f+f-f-f+f
3
Notethatyoucouldcontinuethisprocessforanynumberofiterations.
Afterrewritingthestringthedesirednumberoftimes,replaceeachcharacterthatremainsbysomedrawingcommands.Inthiscase,replacefwithamoveforward(say,by10units),replaceeach+byaclockwiseturnthroughthegivenangle,andreplaceeach-byananticlockwiseturnthroughthegivenangle.
ConvertingL-Systemstofunctionsthatreturnturtlecommandsisstraightforward.Forexample,thefunctioncorrespondingtothis“triangle”L-Systemcanbewrittenasfollows:
triangle::Int->Commandtrianglex=p:#:fxwheref0=Go10
f(x+1)=fx:#:p:#:fx:#:n:#:fx:#:n:#:fx:#:p:#:fxn=Turn90p=Turn(-90)StudytheabovedefinitionandcompareitwiththeL-Systemdefinitiononthepreviouspage.The
abovedefinitionisincludedinLSystem.hs,soyoucantryitoutbytyping(forinstance):
display(triangle5)
Acoupleofthingsareworthnoting.Thesymbolsfromthesystemthatarerewrittenareimple-mentedasfunctionsthattakea“stepnumber”parameter—inthiscase,onlyfisrewritten.Thespecial(x+1)patternallowsustorefereasilytothedecrementedstepnumberasx.Whenwehavetakenthedesirednumberofsteps,thestepnumberbottoms-outat0,andherefisjustinterpretedasadrawingcommand.Thesymbolsthatarenotrewrittenareimplementedas“zero-argument
7
Figure4:TreeL-Systemoutput
functions,”orvariables,suchasnandp.Ingeneral,therewillbeonedefinitioninthewhereclauseforeachletterintheL-System.
ArewriterulefortheL-Systemmaycontainclausesinsquarebrackets,whichcorrespondtobranches.Forexample,hereisasecondL-System,thatusestwolettersandbranches.
angle:start:rewrite:
45f
f→g[-f][+f][gf]g→gg
Hereisthecorrespondingcode(alsoincludedinLSystem.hs.tree::Int->Commandtreex=fxwheref0=GrabPenred:#:Go10
f(x+1)=gx:#:Branch(n:#:fx)
:#:Branch(p:#:fx):#:Branch(gx:#:fx)
g0=GrabPenblue:#:Go10g(x+1)=gx:#:gxn=Turn45p=Turn(-45)
ApicturegeneratedbythisdefinitionisshowninFigure4.
Hereweusedifferentpenstodrawthesegmentsgeneratedbydifferentsymbols:thisisnotpartofthedescriptionoftheL-system,butitgeneratesprettierpictures.
8
Exercises
5.Writeafunctionarrowhead::Int->CommandimplementingthefollowingL-System:
angle:start:rewrite:
60f
f→g+f+gg→f-g-f
6.Writeafunctionsnowflake::Int->CommandimplementingthefollowingL-System:
angle:start:rewrite:
60
f--f--f--f→f+f--f+f
7.Writeafunctionhilbert::Int->CommandimplementingthefollowingL-System:
angle:start:rewrite:
90l
l→+rf-lfl-fr+r→-lf+rfr+fl-
Note:Notallofthesymbolshereneedtomovetheturtle.Checkyourresultagainstthepicturesathttp://en.wikipedia.org/wiki/Hilbert_curveandadjustthefinalvalues(e.g.r0=...)untilitlookslikethose.
BonusL-Systems
Justforfun,herearemoreL-Systemsforyoutotry.
•Peano-Gosper:
angle:start:rewrite:
•Cross
angle:start:rewrite:
•Branch
angle:start:rewrite:
•32-segment
angle:start:rewrite:
90
F+F+F+F
F→-F+F-F-F+F+FF-F+F+FF+F-F-FF+
FF-FF+F+F-FF-F-F+FF-F-F+F+F-F+22.5g
g→f-[[g]+g]+f[+fg]-gf→ff
90
f-f-f-f-f→f-f+f+ff-f-f+f60f
f→f+g++g-f--ff-g+g→-f+gg++g+f--f-g
9
The2008Informatics1ProgrammingCompetition
Youareinvitedtoenterthisyear’sInf1programmingcompetition.Thefirstprizeisabottleofchampagneorabooktokenequivalent.TheprizeissponsoredbyGalois.YoucanseeentriesfrompastyearsontheInformatics1website.
Thecompetitionisoptionalandunassessed.TheprizewillgotothebestpicturegeneratedbyaHaskellprogram,usingturtlecommandsoranythingelseyoucanthinkof.YoumaygeneratethispicturewithanL-Systemorwithanyothertechnique:becreative!Youmayenteraloneorwithagroupofotherstudents.
Mailyourentrytothecourseteachingassistant,includinginstructionsforrunningit;besureitisclearlylabeledwiththenamesofeveryonewhoworkedonit.JudgingwillbebyWillemandPhil.
10
因篇幅问题不能全部显示，请点此查看更多更全内容