Computing Science Functional Programming and

DepartmentofComputingScienceFunctionalProgrammingandGraphAlgorithmsDavidJonathanKingAthesissubmittedforaDoctorofPhilosophyDegreeinComputingScienceattheUniversityofGlasgowMarch1996cDavidJ.King1996AbstractFunctionallanguagesarerenownedfortheirmathematicaltractability,clarityofex-pression,abstractionpowers,andmore.Thereareproblemdomains,however,thatstillpresentrealchallengestofunctionallanguages.Onenotoriouslydicultproblemdomainisgraphalgorithms.GraphalgorithmshavebeenstudiedforalongtimewithconventionalvonNeu-mannlanguages.Theemphasishasprimarilybeenontheeciencyofthealgorithm.Concernssuchasclarityofthealgorithmhavebeensecondary.Althoughtheun-derpinningsofalgorithmsgenerallyhaveasolidtheoreticalfoundation,thereisstillsomedistancebetweencomputerprogramandproofofcorrectness.Thisthesisisaninvestigationofgraphalgorithmsinthenon-strictpurelyfunctionallanguageHaskell.Emphasisisplacedontheimportanceofachievinganasymptoticcomplexityasgoodaswithconventionallanguages.Thisisachievedbyusingthemonadicmodelforincludingactionsonthestate.WorkonthemonadicmodelwascarriedoutatGlasgowUniversitybyWadler,PeytonJones,andLaunchburyintheearlyninetiesandhasopenedupmanydiverseapplicationareas.Oneareaistheabilitytoexpressdatastructuresthatrequiresharing.Althoughgraphsarenotpresentedinthisstyle,datastructuresthatgraphalgorithmsuseareexpressedinthisstyle.Severalexamplesofstatefulalgorithmsaregivenincludingunion/ndfordisjointsets,andthelineartimesortbinsort.Thegraphalgorithmspresentedarenotnew,butaretraditionalalgorithmsrecastinafunctionalsetting.Examplesincludestronglyconnectedcomponents,biconnectedcomponents,Kruskal’sminimumcostspanningtree,andDijkstra’sshortestpaths.Thepresentationislucidgivingmoreinsightthanusual.Thefunctionalsettingallowsforcompletecalculationalstylecorrectnessproofs|whichisdemonstratedwithmanyexamples.Thebenetsofusingafunctionallanguageforexpressinggraphalgorithmsarequan-tiedbylookingattheissuesofexecutiontimes,asymptoticcomplexity,correctness,andclarity,incomparisonwithtraditionalapproaches.Theintentionistobeasobjectiveaspossible,pointingoutboththeweaknessesandthestrengthsofusingafunctionallanguage.ContentsAbstractiiiListofalgorithmsxiPrefacexiiiPrecisofthesis.................................xiiiContributionsofthesis.............................xvAcknowledgements...............................xv1Introduction11.1Graphalgorithmsandfunctionallanguages...............21.2Whygraphalgorithmscanbecomplex.................41.3Traditionalapproaches..........................41.3.1Englishstylepseudo-codepresentations.............41.3.2Functionallanguagepresentations................61.4Imperativefunctionalapproach.....................82Literaturesurvey112.1Graphalgorithmdesign.........................112.1.1Mathematicalinduction.....................112.1.2Usinglibraries...........................122.1.3Graphlanguages.........................13vviContents2.1.4Programderivation........................142.1.5Graphalgebras..........................162.1.6Functionalapproaches......................182.2Algorithmcorrectness...........................202.3Complexityanalysisofalgorithms....................213Functionalalgorithms233.1Treesort..................................243.1.1Transformingthetreesoutoftreesort..............253.1.2Treesortisequivalenttofunctionalquicksort..........263.2Functionalpriorityqueues........................283.3Binomialtrees...............................303.4Implementingbinomialqueuesfunctionally...............313.5Correctnessoffunctionalbinomialqueues................363.5.1Meldmaintainsthebinomialqueuestructure..........363.5.2Meldmaintainstheheap-orderingproperty...........403.5.3Meldmeetsitsspecication...................423.6ImplementingdecreaseKeyanddelete................433.7Comparisonwithotherpriorityqueues.................444Statefulalgorithms474.1Theneedforstate............................474.2Includingimperativeactionsinafunctionallanguage.........484.3Statetransformers............................494.3.1Thedonotation..........................494.4Variables..................................504.5Explicitlylinkedlists...........................514.5.1Queues...............................534.5.2Hidingthequeue.........................55Contentsvii4.6Mutablearrays..............................564.7Binsort...................................574.8Disjointsets(union/nd).........................584.9Statefulcombinators...........................624.10Discussion.................................644.11Relatedwork...............................665Modellinggraphs695.1Representationsofgraphs........................695.2Cyclicrepresentations..........................705.3Adjacencylists..............................715.4Classifyinggraphs.............................745.4.1Classifyingundirectedgraphs..................755.4.2Generatinggraphs........................765.4.3Generatingrandomgraphs....................785.5Adjacencymatrices............................795.5.1Classifyingedgelabelledgraphs................