Advanced Functional Programming

thetheorybehindmanythingscommonlywrittenbyfunctionalprogrammers. Oneofthemainachievementsoftheprojecthasbeentomakepeopleaware ofthefactthatmanyalgorithmscanbedescribedinadata-independentway. ThePolyPsystemintroducedinthesenotesisoneofthetranslationstothe Haskell-worldofthistheoreticalunderpinning. Thethirdlecture,onGenericProgramTransformation,canalsobeseenas anapplicationofthetheoryintroducedinlecturetwo. Manye?ciency-improving programtransformationscanbeperformedinamechanicalway,andthesewould nothavebeenpossiblewithoutinsightintothecorrectnessofsuchtransfor- tionsgainedinthelectureonGenericProgramming. Thefourthlecture,onDesigningandImplementingCombinatorLanguages, introducesaneasytowriteformalismforwritingdownthecatamorphismsint- ducedinearlierchapters. Itisshownhowquitecomplicatedcatamorphisms,that at?rstsightseemratherforbiddingbymakingextensiveuseofhigher-orderdo- VI Preface mains,canactuallybedevelopedinastep-wisefashion,usinganattributegr- marview;itisfurthermoreshownhowtorelatethiswayofprogrammingwith conceptsfromtheobject-orientedworldthusmakingclearwhatthestrengths andweaknessesofeachworldare. The?fthlecture,titledUsingMetaML:AStagedProgrammingLanguage, introducestheconceptofpartialevaluation. Itservesasanotherinstanceof thequestfor“themostgenericofwritingprogramsatthelowestcost”. The stagingtechniquesshowhowcoststhatwereintroducedbyaddingextralevels ofabstraction,maybemovedfromrun-timetocompile-time. Ithasbeencommonknowledgetousersofmodernfunctionallanguagesthat thetypesystemcanbeagreathelpinshorteningprogramsandreducingerrors. Intheextremeonemightseeatypeasapredicatecapturingtheproperties ofanyexpressionwiththattype. InthesixthlectureonCayenne–Spiceup yourProgrammingwithDependentTypesitisshowninwhatdirectionfunctional languagesaremostlikelytodevelop,andwhatmaybeexpectedofthenewtype systemstobeintroduced. Thelastlecture,titledHaskellasanAutomationController,showsthat writingfunctionalprogramsdoesnothavetoimplythatoneisboundtoremain isolatedfromtherestoftheworld. Beingabletocommunicatewithsoftware writtenbyothersinauniformway,isprobablyoneofthemostinteresting newdevelopmentsincurrentcomputerscience. Itappearsthattheconceptofa monadtogetherwiththeHaskelltypingrules,isquiteadequatetodescribethe interfacebetweenHaskellprogramsandtheouterworld. Finallywewanttothankeveryonewhocontributedtothisschoolandmade itsuchasuccessfulevent:sponsors,localsystemmanagers,localorganizers, students,andlastbutnotleastthelecturers. Weareconvincedthateveryone presentattheschoolenjoyedthiseventasmuchaswedid,andweallhopethat youwillfeelsomeofthespiritofthiseventwhenstudyingtheselecturenotes. March1999 DoaitseSwierstra PedroHenriques Jos´eOliveira VII Sponsorship Theschoolhasreceivedgeneroussponsorshipfrom: FCT-Fundac˜¸aoparaaCiˆenciaeTecnologia,Minist´eriodaCiˆenciae Tecnologia AdegaCooperativadePontedeLima AgˆenciaAbreu CGD-CaixaGeraldeDep´ositos CIUM-CentrodeInform´aticadaUniversidadedoMinho DI-DepartamentodeInform´aticadaUniversidadedoMinho GEPL-GrupodeEspeci?cac˜¸aoeProcessamentodeLinguagens LESI-Direc¸c˜aodeCursodeEngenhariadeSistemaseInform´atica Enabler Lactolima Latic´?niosdasMarinhas,Lda NovabasePorto-SistemasdeInforma¸c˜aoSA PrimaveraSoftware ProjectoCamila-GrupodeM´etodosFormais Sidereus-SistemasdeInforma¸c˜aoeConsultoriaInformat´icaLda SIBS-SociedadeInterbanc´ariadeServico¸s VieiradeCastro LocalCommittee: Jos´eAlmeida,Minho Lu´?sBarbosa,Minho Jos´eBarros,Minho M. Joao ˜ Frade,Minho PedroHenriques,Minho F. M´arioMartins,Minho F. LuisNeves,Minho CarlaOliveira,Minho JorgePinto,Lix JorgeRocha,Minho CesarRodrigues,Minho Joa˜oSaraiva,Minho M. Joa˜oVaranda,Minho IX TableofContents SortingMorphisms. 1 LexAugusteijn 1 Introduction. 1 2 MorphismsonLists. 2 2. 1 TheListCatamorphism. 2 2. 2 TheListAnamorphism. 4 2. 3 TheListHylomorphism. 5 2. 4 InsertionSort. 6 2. 5 SelectionSorts. 7 3 LeafTrees. 9 3. 1 TheLeaf-TreeCatamorphism. 9 3. 2 TheLeaf-TreeAnamorphism. 10 3. 3 TheLeaf-TreeHylomorphism. 11 3. 4 MergeSort. 12 4 BinaryTrees. 13 4. 1 TheTreeCatamorphism. 13 4. 2 TheTreeAnamorphism. 14 4. 3 TheTreeHylomorphism. 14 4. 4 Quicksort. 15 4. 5 HeapSort. 16 5 Paramorphisms. 18 5. 1 TheListParamorphism. 18 5. 2 InsertAsParamorphism. 18 5. 3 RemoveAsParamorphism. 19 6 GeneralizingDataStructures. 20 6. 1 GeneralizingQuicksort. 20 6. 2 GeneralizingHeapSort. 21 7 Conclusions. 23 GenericProgramming–AnIntroduction–. 28 RolandBackhouse,PatrikJansson,JohanJeuring,LambertMeertens 1 Introduction.