haskell-tutorial

AGentleIntroductiontoHaskell98PaulHudakYaleUniversityDepartmentofComputerScienceJohnPetersonYaleUniversityDepartmentofComputerScienceJosephH.FaselUniversityofCaliforniaLosAlamosNationalLaboratoryOctober,1999Copyrightc1999PaulHudak,JohnPetersonandJosephFaselPermissionisherebygranted,freeofcharge,toanypersonobtainingacopyof\AGentleIntroductiontoHaskell(theText),todealintheTextwithoutrestriction,includingwithoutlimitationtherightstouse,copy,modify,merge,publish,distribute,sublicense,and/orsellcopiesoftheText,andtopermitpersonstowhomtheTextisfurnishedtodoso,subjecttothefollowingcondition:TheabovecopyrightnoticeandthispermissionnoticeshallbeincludedinallcopiesorsubstantialportionsoftheText.1IntroductionOurpurposeinwritingthistutorialisnottoteachprogramming,noreventoteachfunctionalprogramming.Rather,itisintendedtoserveasasupplementtotheHaskellReport[4],whichisotherwisearatherdensetechnicalexposition.OurgoalistoprovideagentleintroductiontoHaskellforsomeonewhohasexperiencewithatleastoneotherlanguage,preferablyafunctionallanguage(evenifonlyan\almost-functionallanguagesuchasMLorScheme).Ifthereaderwishestolearnmoreaboutthefunctionalprogrammingstyle,wehighlyrecommendBird’stextIntroductiontoFunctionalProgramming[1]orDavie’sAnIntroductiontoFunctionalProgrammingSystemsUsingHaskell[2].Forausefulsurveyoffunctionalprogramminglanguagesandtechniques,includingsomeofthelanguagedesignprinciplesusedinHaskell,see[3].TheHaskelllanguagehasevolvedsignicantlysinceitsbirthin1987.ThistutorialdealswithHaskell98.Olderversionsofthelanguagearenowobsolete;HaskellusersareencouragedtouseHaskell98.TherearealsomanyextensionstoHaskell98thathavebeenwidelyimplemented.ThesearenotyetaformalpartoftheHaskelllanguageandarenotcoveredinthistutorial.Ourgeneralstrategyforintroducinglanguagefeaturesisthis:motivatetheidea,denesometerms,givesomeexamples,andthenpointtotheReportfordetails.Wesuggest,however,thatthereadercompletelyignorethedetailsuntiltheGentleIntroductionhasbeencompletelyread.Onthe122VALUES,TYPES,ANDOTHERGOODIESotherhand,Haskell’sStandardPrelude(inAppendixAoftheReportandthestandardlibraries(foundintheLibraryReport[5])containlotsofusefulexamplesofHaskellcode;weencourageathoroughreadingoncethistutorialiscompleted.ThiswillnotonlygivethereaderafeelforwhatrealHaskellcodelookslike,butwillalsofamiliarizeherwithHaskell’sstandardsetofpredenedfunctionsandtypes.Finally,theHaskellwebsite,[Wehavealsotakenthecourseofnotlayingoutaplethoraoflexicalsyntaxrulesattheoutset.Rather,weintroducethemincrementallyasourexamplesdemand,andenclosetheminbrackets,aswiththisparagraph.ThisisinstarkcontrasttotheorganizationoftheReport,althoughtheReportremainstheauthoritativesourcefordetails(referencessuchas\x2.1refertosectionsintheReport).]Haskellisatypefulprogramminglanguage:1typesarepervasive,andthenewcomerisbestobecomingwellawareofthefullpowerandcomplexityofHaskell’stypesystemfromtheoutset.Forthosewhoseonlyexperienceiswithrelatively\untypefullanguagessuchasPerl,Tcl,orScheme,thismaybeadiÆcultadjustment;forthosefamiliarwithJava,C,Modula,orevenML,theadjustmentshouldbeeasierbutstillnotinsignicant,sinceHaskell’stypesystemisdierentandsomewhatricherthanmost.Inanycase,\typefulprogrammingispartoftheHaskellprogrammingexperience,andcannotbeavoided.2Values,Types,andOtherGoodiesBecauseHaskellisapurelyfunctionallanguage,allcomputationsaredoneviatheevaluationofexpressions(syntacticterms)toyieldvalues(abstractentitiesthatweregardasanswers).Everyvaluehasanassociatedtype.(Intuitively,wecanthinkoftypesassetsofvalues.)Examplesofexpressionsincludeatomicvaluessuchastheinteger5,thecharacter’a’,andthefunction\x-x+1,aswellasstructuredvaluessuchasthelist[1,2,3]andthepair(’b’,4).Justasexpressionsdenotevalues,typeexpressionsaresyntactictermsthatdenotetypevalues(orjusttypes).ExamplesoftypeexpressionsincludetheatomictypesInteger(innite-precisionintegers),Char(characters),Integer-Integer(functionsmappingIntegertoInteger),aswellasthestructuredtypes[Integer](homogeneouslistsofintegers)and(Char,Integer)(character,integerpairs).AllHaskellvaluesare\rst-class|theymaybepassedasargumentstofunctions,returnedasresults,placedindatastructures,etc.Haskelltypes,ontheotherhand,arenotrst-class.Typesinasensedescribevalues,andtheassociationofavaluewithitstypeiscalledatyping.Usingtheexamplesofvaluesandtypesabove,wewritetypingsasfollows:5::Integer’a’::Charinc::Integer-Integer[1,2,3]::[Integer](’b’,4)::(Char,Integer)1CoinedbyLucaCardelli.2.1PolymorphicTypes3The\::canberead\hastype.FunctionsinHaskellarenormallydenedbyaseriesofequations.Forexample,thefunctioninccanbedenedbythesingleequation:incn=n+1Anequationisanexampleofadeclaration.Anotherkindofdeclarationisatypesignaturedecla-ration(x4.4.1),withwhichwecandeclareanexplicittypingforinc:inc::Integer-IntegerWewillhavemuchmoretosayaboutfunctiondenitionsinSection3.Forpedagogicalpurposes,whenwewishtoindicatethatanexpressione1evaluates,or\re-duces,toanotherexpressionorvaluee2,wewillw