资源描述:
《Purely Functional Data Structures.pdf》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、PURELYFUNCTIONALDATASTRUCTURESMostbooksondatastructuresassumeanimperativelanguagelikeCorC++.However,datastructuresfortheselanguagesdonotalwaystranslatewelltofunctionallanguagessuchasStandardML,Haskell,orScheme.Thisbookdescribesdatastructuresfromthepointofviewoffunctionallan
2、guages,withexamples,andpresentsdesigntechniquessothatprogrammerscandeveloptheirownfunctionaldatastructures.Itincludesbothclassicaldatastructures,suchasred-blacktreesandbinomialqueues,andahostofnewdatastructuresdevelopedexclusivelyforfunctionallanguages.Allsourcecodeisgiveni
3、nStandardMLandHaskell,andmostoftheprogramscaneasilybeadaptedtootherfunctionallanguages.Thishandyreferenceforprofessionalprogrammersworkingwithfunctionallanguagescanalsobeusedasatutorialorforself-study.PURELYFUNCTIONALDATASTRUCTURESCHRISOKASAKICOLUMBIAUNIVERSITYCAMBRIDGEUNIV
4、ERSITYPRESSPUBLISHEDBYTHEPRESSSYNDICATEOFTHEUNIVERSITYOFCAMBRIDGEThePittBuilding,TrumpingtonStreet,Cambridge,UnitedKingdomCAMBRIDGEUNIVERSITYPRESSTheEdinburghBuilding,CambridgeCB22RU,UKwww.cup.cam.ac.uk40West20thStreet,NewYork,NY10011-4211,USAwww.cup.org10StamfordRoad,Oakle
5、igh,Melbourne3166,AustraliaRuizdeAlarc6n13,28014Madrid,Spain©CambridgeUniversityPress1998Thisbookisincopyright.Subjecttostatutoryexceptionandtotheprovisionsofrelevantcollectivelicensingagreements,noreproductionofanypartmaytakeplacewithoutthewrittenpermissionofCambridgeUnive
6、rsityPress.Firstpublished1998Firstpaperbackedition1999TypefaceTimes10/13pt.AcatalogrecordforthisbookisavailablefromtheBritishLibraryLibraryofCongressCataloginginPublicationdataisavailableISBN0521631246hardbackISBN0521663504paperbackTransferredtodigitalprinting2003ContentsPr
7、efacepageixIntroduction11.1Functionalvs.ImperativeDataStructures11.2Strictvs.LazyEvaluation21.3Terminology31.4Approach41.5Overview4Persistence72.1Lists72.2BinarySearchTrees112.3ChapterNotes15SomeFamiliarDataStructuresinaFunctionalSetting173.1LeftistHeaps173.2BinomialHeaps20
8、3.3Red-BlackTrees243.4ChapterNotes29LazyEvaluation314.1$-notation314.2Streams344.3