# A gentle introduction to Haskell 98.pdf

A Gentle Introduction to Haskell 98Paul HudakYale UniversityDepartment of Computer ScienceJohn PetersonYale UniversityDepartment of Computer ScienceJoseph H. FaselUniversity of CaliforniaLos Alamos National LaboratoryOctober, 1999Copyright c© 1999 Paul Hudak, John Peterson and Joseph FaselPermission is hereby granted, free of charge, to any person obtaining a copy of “A GentleIntroduction to Haskell” (the Text), to deal in the Text without restriction, including withoutlimitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sellcopies of the Text, and to permit persons to whom the Text is furnished to do so, subject to thefollowing condition: The above copyright notice and this permission notice shall be included inall copies or substantial portions of the Text.1 IntroductionOur purpose in writing this tutorial is not to teach programming, nor even to teach functionalprogramming. Rather, it is intended to serve as a supplement to the Haskell Report [4], whichis otherwise a rather dense technical exposition. Our goal is to provide a gentle introduction toHaskell for someone who has experience with at least one other language, preferably a functionallanguage (even if only an “almost-functional” language such as ML or Scheme). If the readerwishes to learn more about the functional programming style, we highly recommend Bird’s textIntroduction to Functional Programming [1] or Davie’s An Introduction to Functional Program-ming Systems Using Haskell [2]. For a useful survey of functional programming languages andtechniques, including some of the language design principles used in Haskell, see [3].The Haskell language has evolved significantly since its birth in 1987. This tutorial deals withHaskell 98. Older versions of the language are now obsolete; Haskell users are encouraged to useHaskell 98. There are also many extensions to Haskell 98 that have been widely implemented.These are not yet a formal part of the Haskell language and are not covered in this tutorial.Our general strategy for introducing language features is this: motivate the idea, define someterms, give some examples, and then point to the Report for details. We suggest, however, thatthe reader completely ignore the details until the Gentle Introduction has been completely read.On the other hand, Haskell’s Standard Prelude (in Appendix A of the Report and the standardlibraries (found in the Library Report [5]) contain lots of useful examples of Haskell code; weencourage a thorough reading once this tutorial is completed. This will not only give the readera feel for what real Haskell code looks like, but will also familiarize her with Haskell’s standardset of predefined functions and types.12 VALUES, TYPES, AND OTHER GOODIES 2Finally, the Haskell web site, http://haskell.org, has a wealth of information about theHaskell language and its implementations.[We have also taken the course of not laying out a plethora of lexical syntax rules at theoutset. Rather, we introduce them incrementally as our examples demand, and enclose themin brackets, as with this paragraph. This is in stark contrast to the organization of the Report,although the Report remains the authoritative source for details (references such as “§2.1” referto sections in the Report).]Haskell is a typeful programming language:1 types are pervasive, and the newcomer is bestoff becoming well aware of the full power and complexity of Haskell’s type system from theoutset. For those whose only experience is with relatively “untypeful” languages such as Perl,Tcl, or Scheme, this may be a difficult adjustment; for those familiar with Java, C, Modula, oreven ML, the adjustment should be easier but still not insignificant, since Haskell’s type systemis different and somewhat richer than most. In any case, “typeful programming” is part of theHaskell programming experience, and cannot be avoided.2 Values, Types, and Other GoodiesBecause Haskell is a purely functional language, all computations are done via the evaluation ofexpressions (syntactic terms) to yield values (abstract entities that we regard as answers). Everyvalue has an associated type. (Intuitively, we can think of types as sets of values.) Examplesof expressions include atomic values such as the integer 5, the character ’a’, and the function\x - x+1, as well as structured values such as the list [1,2,3] and the pair (’b’,4).Just as expressions denote values, type expressions are syntactic terms that denote typevalues (or just types). Examples of type expressions include the atomic types Integer (infinite-precision integers), Char (characters), Integer-Integer (functions mapping Integer to Integer),as well as the structured types [Integer] (homogeneous lists of integers) and (Char,Integer)(character, integer pairs).All Haskell values are “first-class”—they may be passed as arguments to functions, returnedas results, placed in data structures, etc. Haskell types, on the other hand, are not first-class.Types in a sense describe values, and the association of a value with its type is called a typing.Using the examples of values and types above, we write typings as follows:5 :: Integer’a’ :: Charinc :: Integer - Integer[1,2,3] :: [Integer](’b’,4) :: (Char,Integer)The “::” can be read “has type.”Functions in Haskell are normally defined by a series of equations. For example, the functioninc can be defined by the single equation:inc n = n+1An equation is an example of a declaration. Another kind of declaration is a type signaturedeclaration (§4.4.1), with which we can declare an explicit typing for inc:inc :: Integer - IntegerWe will have much more to say about function definitions in Section 3.1Coined by Luca Cardelli.2 VALUES, TYPES, AND OTHER GOODIES 3For pedagogical purposes, when we wish to indicate that an expression e1 evaluates, or“reduces,” to another expression or value e2, we will write:e1 ⇒ e2For example, note that:inc (inc 3) ⇒ 5Haskell’s static type system defines the formal relationship between types and values (§4.1.3).The static type system ensures that Haskell programs are type safe; that is, that the programmerhas not mismatched types in some way. For example, we cannot generally add together twocharacters, so the expression ’a’+’b’ is ill-typed. The main advantage of statically typedlanguages is well-known: All type errors are detected at compile-time. Not all errors are caughtby the type system; an expression such as 1/0 is typable but its evaluation will result in an errorat execution time. Still, the type system finds many program errors at compile time, aids theuser in reasoning about programs, and also permits a compiler to generate more efficient code(for example, no run-time type tags or tests are required).The type system also ensures that user-supplied type signatures are correct. In fact, Haskell’stype system is powerful enough to allow us to avoid writing any type signatures at all;2 we saythat the type system infers the correct types for us. Nevertheless, judicious placement of typesignatures such as that we gave for inc is a good idea, since type signatures are a very effectiveform of documentation and help bring programming errors to light.[The reader will note that we have capitalized identifiers that denote specific types, suchas Integer and Char, but not identifiers that denote values, such as inc. This is not just aconvention: it is enforced by Haskell’s lexical syntax. In fact, the case of the other charactersmatters, too: foo, fOo, and fOO are all distinct identifiers.]2.1 Polymorphic TypesHaskell also incorporates polymorphic types—types that are universally quantified in some wayover all types. Polymorphic type expressions essentially describe families of types. For example,(∀a)[a] is the family of types consisting of, for every type a, the type of lists of a. Lists ofintegers (e.g. [1,2,3]), lists of characters ([’a’,’b’,’c’]), even lists of lists of integers, etc.,are all members of this family. (Note, however, that [2,’b’] is not a valid example, since thereis no single type that contains both 2 and ’b’.)[Identifiers such as a above are called type variables, and are uncapitalized to distinguishthem from specific types such as Int. Furthermore, since Haskell has only universally quantifiedtypes, there is no need to explicitly write out the symbol for universal quantification, and thuswe simply write [a] in the example above. In other words, all type variables are implicitlyuniversally quantified.]Lists are a commonly used data structure in functional languages, and are a good vehicle forexplaining the principles of polymorphism. The list [1,2,3] in Haskell is actually shorthandfor the list 1:(2:(3:[])), where [] is the empty list and : is the infix operator that adds itsfirst argument to the front of its second argument (a list).3 Since : is right associative, we canalso write this list as 1:2:3:[].As an example of a user-defined function that operates on lists, consider the problem ofcounting the number of elements in a list:2With a few exceptions to be described later.3: and [] are like Lisp’s cons and nil, respectively.2 VALUES, TYPES, AND OTHER GOODIES 4length :: [a] - Integerlength [] = 0length (x:xs) = 1 + length xsThis definition is almost self-explanatory. We can read the equations as saying: “The length ofthe empty list is 0, and the length of a list whose first element is x and remainder is xs is 1 plusthe length of xs.” (Note the naming convention used here; xs is the plural of x, and should beread that way.)Although intuitive, this example highlights an important aspect of Haskell that is yet to beexplained: pattern matching. The left-hand sides of the equations contain patterns such as []and x:xs. In a function application these patterns are matched against actual parameters in afairly intuitive way ([] only matches the empty list, and x:xs will successfully match any listwith at least one element, binding x to the first element and xs to the rest of the list). If thematch succeeds, the right-hand side is evaluated and returned as the result of the application.If it fails, the next equation is tried, and if all equations fail, an error results.Defining functions by pattern matching is quite common in Haskell, and the user shouldbecome familiar with the various kinds of patterns that are allowed; we will return to this issuein Section 4.The length function is also an example of a polymorphic function. It can be applied to alist containing elements of any type, for example [Integer], [Char], or [[Integer]].length [1,2,3] ⇒ 3length [’a’,’b’,’c’] ⇒ 3length [[1],[2],[3]] ⇒ 3Here are two other useful polymorphic functions on lists that will be used later. Functionhead returns the first element of a list, function tail returns all but the first.head :: [a] - ahead (x:xs) = xtail :: [a] - [a]tail (x:xs) = xsUnlike length, these functions are not defined for all possible values of their argument. Aruntime error occurs when these functions are applied to an empty list.With polymorphic types, we find that some types are in a sense strictly more general thanothers in the sense that the set of values they define is larger. For example, the type [a] is moregeneral than [Char]. In other words, the latter type can be derived from the former by a suitablesubstitution for a. With regard to this generalization ordering, Haskell’s type system possessestwo important properties: First, every well-typed expression is guaranteed to have a uniqueprincipal type (explained below), and second, the principal type can be inferred automatically(§4.1.3). In comparison to a monomorphically typed language such as C, the reader will findthat polymorphism improves expressiveness, and type inference lessens the burden of types onthe programmer.An expression’s or function’s principal type is the least general type that, intuitively, “con-tains all instances of the expression”. For example, the principal type of head is [a]-a; [b]-a,a-a, or even a are correct types, but too general, whereas something like [Integer]-Integeris too specific. The existence of unique principal types is the hallmark feature of the Hindley-Milner type system, which forms the basis of the type systems of Haskell, ML, Miranda,4 andseveral other (mostly functional) languages.4“Miranda” is a trademark of Research Software, Ltd.2 VALUES, TYPES, AND OTHER GOODIES 52.2 User-Defined TypesWe can define our own types in Haskell using a data declaration, which we introduce via a seriesof examples (§4.2.1).An important predefined type in Haskell is that of truth values:data Bool = False | TrueThe type being defined here is Bool, and it has exactly two values: True and False. TypeBool is an example of a (nullary) type constructor, and True and False are (also nullary) dataconstructors (or just constructors, for short).Similarly, we might wish to define a color type:data Color = Red | Green | Blue | Indigo | VioletBoth Bool and Color are examples of enumerated types, since they consist of a finite numberof nullary data constructors.Here is an example of a type with just one data constructor:data Point a = Pt a aBecause of the single constructor, a type like Point is often called a tuple type, since it isessentially just a cartesian product (in this case binary) of other types.5 In contrast, multi-constructor types, such as Bool and Color, are called (disjoint) union or sum types.More importantly, however, Point is an example of a polymorphic type: for any type t,it defines the type of cartesian points that use t as the coordinate type. The Point type cannow be seen clearly as a unary type constructor, since from the type t it constructs a new typePoint t. (In the same sense, using the list example given earlier, [] is also a type constructor.Given any type t we can “apply” [] to yield a new type [t]. The Haskell syntax allows [] t tobe written as [t]. Similarly, - is a type constructor: given two types t and u, t-u is the typeof functions mapping elements of type t to elements of type u.)Note that the type of the binary data constructor Pt is a - a - Point a, and thus thefollowing typings are valid:Pt 2.0 3.0 :: Point FloatPt ’a’ ’b’ :: Point CharPt True False :: Point BoolOn the other hand, an expression such as Pt ’a’ 1 is ill-typed because ’a’ and 1 are of differenttypes.It is important to distinguish between applying a data constructor to yield a value, andapplying a type constructor to yield a type; the former happens at run-time and is how wecompute things in Haskell, whereas the latter happens at compile-time and is part of the typesystem’s process of ensuring type safety.[Type constructors such as Point and data constructors such as Pt are in separate names-paces. This allows the same name to be used for both a type constructor and data constructor,as in the following:data Point a = Point a aWhile this may seem a little confusing at first, it serves to make the link between a type and itsdata constructor more obvious.]5Tup