A gentle introduction to Haskell 98

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-functional”languagesuchasMLorScheme).Ifthereaderwishestolearnmoreaboutthefunctionalprogrammingstyle,wehighlyrecommendBird’stextIntroductiontoFunctionalProgramming[1]orDavie’sAnIntroductiontoFunctionalProgram-mingSystemsUsingHaskell[2].Forausefulsurveyoffunctionalprogramminglanguagesandtechniques,includingsomeofthelanguagedesignprinciplesusedinHaskell,see[3].TheHaskelllanguagehasevolvedsignificantlysinceitsbirthin1987.ThistutorialdealswithHaskell98.Olderversionsofthelanguagearenowobsolete;HaskellusersareencouragedtouseHaskell98.TherearealsomanyextensionstoHaskell98thathavebeenwidelyimplemented.ThesearenotyetaformalpartoftheHaskelllanguageandarenotcoveredinthistutorial.Ourgeneralstrategyforintroducinglanguagefeaturesisthis:motivatetheidea,definesometerms,givesomeexamples,andthenpointtotheReportfordetails.Wesuggest,however,thatthereadercompletelyignorethedetailsuntiltheGentleIntroductionhasbeencompletelyread.Ontheotherhand,Haskell’sStandardPrelude(inAppendixAoftheReportandthestandardlibraries(foundintheLibraryReport[5])containlotsofusefulexamplesofHaskellcode;weencourageathoroughreadingoncethistutorialiscompleted.ThiswillnotonlygivethereaderafeelforwhatrealHaskellcodelookslike,butwillalsofamiliarizeherwithHaskell’sstandardsetofpredefinedfunctionsandtypes.12VALUES,TYPES,ANDOTHERGOODIES2Finally,theHaskellwebsite,[Wehavealsotakenthecourseofnotlayingoutaplethoraoflexicalsyntaxrulesattheoutset.Rather,weintroducethemincrementallyasourexamplesdemand,andenclosetheminbrackets,aswiththisparagraph.ThisisinstarkcontrasttotheorganizationoftheReport,althoughtheReportremainstheauthoritativesourcefordetails(referencessuchas“§2.1”refertosectionsintheReport).]Haskellisatypefulprogramminglanguage:1typesarepervasive,andthenewcomerisbestoffbecomingwellawareofthefullpowerandcomplexityofHaskell’stypesystemfromtheoutset.Forthosewhoseonlyexperienceiswithrelatively“untypeful”languagessuchasPerl,Tcl,orScheme,thismaybeadifficultadjustment;forthosefamiliarwithJava,C,Modula,orevenML,theadjustmentshouldbeeasierbutstillnotinsignificant,sinceHaskell’stypesystemisdifferentandsomewhatricherthanmost.Inanycase,“typefulprogramming”ispartoftheHaskellprogrammingexperience,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(infinite-precisionintegers),Char(characters),Integer-Integer(functionsmappingIntegertoInteger),aswellasthestructuredtypes[Integer](homogeneouslistsofintegers)and(Char,Integer)(character,integerpairs).AllHaskellvaluesare“first-class”—theymaybepassedasargumentstofunctions,returnedasresults,placedindatastructures,etc.Haskelltypes,ontheotherhand,arenotfirst-class.Typesinasensedescribevalues,andtheassociationofavaluewithitstypeiscalledatyping.Usingtheexamplesofvaluesandtypesabove,wewritetypingsasfollows:5::Integer’a’::Charinc::Integer-Integer[1,2,3]::[Integer](’b’,4)::(Char,Integer)The“::”canberead“hastype.”FunctionsinHaskellarenormallydefinedbyaseriesofequations.Forexample,thefunctioninccanbedefinedbythesingleequation:incn=n+1Anequationisanexampleofadeclaration.Anotherkindofdeclarationisatypesignaturedeclaration(§4.4.1),withwhichwecandeclareanexplicittypingforinc:inc::Integer-IntegerWewillhavemuchmoretosayaboutfunctiondefinitionsinSection3.1CoinedbyLucaCardelli.2VALUES,TYPES,ANDOTHERGOODIES3Forpedagogicalpurposes,whenwewishtoindicatethatanexpressione1evaluates,or“reduces,”toanotherexpression