Functional programming is a programming style that emphasizes the use of functions (in contrast to object-oriented programming, which emphasizes the use of objects). It has become popular in recent years because of its simplicity, conciseness, and clarity. This book teaches functional programming using Haskell, the most popular purely functional language. The emphasis is on functional programming as a way of thinking and problem solving, using Haskell as a vehicle for expressing solutions. Rather than using conventional - arguably boring - examples from mathematics, which are commonly found in other programming language books, this tutorial uses examples drawn from multimedia applications, including graphics, animation, and computer music, thus rewarding the reader with working programs for inherently more interesting applications. The author also teaches how to reason about functional programs, using a very simple process of calculation.

Aimed at both beginning and advanced programmers, this tutorial begins with a gentle introduction to functional programming, including basic ideas such as values, types, pattern matching, recursion, higher-order functions, data structures, polymorphism, abstraction, lazy evaluation, and proof by calculation. It then moves rapidly on to more advanced topics, such as infinite data structures, type classes, higher-order types, IO, monads, and inductive proofs. Details about programming in Haskell are presented in boxes throughout the text for easy reference.

Paul Hudak is Professor of Computer Science at Yale University. He was instrumental in organizing and chairing the Haskell Committee, an international group of computer scientists who designed Haskell, a nonstrict, pure functional programming language. He is a cofounder and editor of the Journal of Functional Programming. He has published over 100 papers on the design and application of programming languages.

Hudak believes that programming languages should be pushed further in the direction of high-level abstractions, in which the programmer says less about the details of a computation and more about the problem specification itself. At the same time, he recognizes the need for smart compilation techniques to make such languages practical. His most recent interest is in applying these principles to multimedia technology, including computer music, graphics and animation, and robotics.

The first high-level languages developed for general purpose programming were Fortran (Backus, 1978) and Lisp (McCarthy, 1978), developed in the late 1950s by John Backus and John McCarthy, respectively. From Fortran grew many of today's modern imperative languages, most of which did not improve significantly on the fundamental ideas found in the language Algol (de Morgan, Hill and Wichmann, 1976), which shortly followed Fortran. The Lisp family was less fecund, perhaps because it was so far ahead of its time, but was the seed for the family of functional languages about which this textbook was written. The most radical in this class of languages is probably Haskell originally designed in the late 1980s (Hudak, Wadler, 1988) based on, at that point, a good ten years of experience designing and implementing similar languages, most notably a series of languages developed by David Turner in the late 1970s and early 1980s (Turner, 1976; 1985). Although research continues on the design of Haskell, the version used in this textbook, Haskell 98 (Augustsson, et al., 1999), is the latest and most stable version of the language and its libraries.

Haskell was named after the logician Haskell B. Curry who, along with Alonzo Church, established the theoretical foundations of functional programming back when computers themselves were only a gleam in researchers' eyes. A curious historical fact is that Haskell Curry's father, Samuel Silas Curry, helped to found and direct a school in Boston called the School of Expression. Because pure functional programming centers around the notion of an expression, I thought that The Haskell School of Expression would be a good title for this book.

It's hard to predict just how it is that a language becomes popular. Fortran became popular because it was the first high-level language and a welcome alternative to assembly language, and ultimately because it was a good vehicle for coding numerical algorithms in the domain of scientific computing. C (Kernighan and Ritchie, 1978) was not revolutionary by any means, often being described as a high-level assembly language. But it found a niche in Unix and systems-level programming, and from there to other operating system platforms. Cobol (Cobol, 1968) was designed from day one for business applications, and so made its mark. Java's (Gosling, Joy and Steele, 1996) recent astonishing rise in popularity is rather perplexing on one hand, yet quite understandable on another. As a language, it is simple and elegant, but certainly not revolutionary. Yet it found a niche in its use on the world-wide-web, which at the time was (and still is) a phenomenon in its own right. Lisp and Scheme (Rees and Clinger, 1986) for AI, Ada (Ada,79) for real-time applications, VHDL and Verilog for digital hardware design, and the list goes on.

From this discussion it appears that for a language to become popular it needs an application - a niche - in which it excels, or in which it at least was the first to arrive. Curiously, for most language designers, this is the opposite of what is desired. Most language designers would like their languages to be truly general purpose, able to solve all of the world's problems with great succinctness, clarity, and efficiency. As a result, many excellent languages out there, some with very decent implementations, will probably forever remain in obscurity because they never found their niche.

Although the designers of Haskell exhibited no exception to this ambitious approach to language design, in retrospect I wonder if there might be a plausible niche for Haskell. These sorts of things are mostly out of my control, of course, but I thought it would be fun to use multimedia - graphics, sound, and animation - as an underlying theme, embodied concretely through many examples and exercises, in this text. Multimedia is an application area that is certainly current and important, and one in which Haskell's advantages are highly visible.

In addition, one of the nice things about multimedia programming is that all of the really interesting (and hard!) problems faced by computer scientists over the past 30 years are found in the "virtual worlds" that we create. Nondeterminism, concurrency, state, time, efficiency, decidability, and others are all issues that must be addressed. Although I don't cover all of these issues in this text, multimedia programming nevertheless provides a good vehicle through which one could teach general topics in computer science.

I also hope that this text demonstrates the ease with which one can embed a domain-specific language in Haskell. In a more general sense, this might actually be the most profitable niche for Haskell, as there have been a number of success stories in this area already.

In any case, I hope that you enjoy working through the various multimedia programs as much as I have enjoyed creating them. At the same time, I hope that this text might help Haskell to find its niche and thus avoid the fate of obscurity described earlier. Haskell really is a beautiful language.

At the time I began writing this book there were not many other books about programming specifically in Haskell. But that wasn't the main reason I decided to tackle this task. More importantly, there was a need for a book that described how to solve problems using a functional language such as Haskell. As with any major class of languages, there is a certain mind-set for contemplation, a certain viewpoint of the world, and a certain approach to problem solving that collectively work best. If you teach only Haskell language details to a C programmer, she is likely to write very ugly, incomprehensible functional programs. But if you teach her how to think differently, how to see problems in a different light, functional solutions will come easily, and elegant Haskell programs will result. That, in a nutshell, is my goal in this textbook. As Samuel Silas Curry once said:

All of the material in this textbook can be covered in one semester as an advanced undergraduate course. For lower-level courses, including possible use in high school, some of the mathematics may cause problems, but for bright students I suspect most of the material can still be covered.

I strongly encourage sticking to the order of the chapters in the book, which introduces Haskell language features as they are demanded by the underlying application themes (generally the chapters alternate between "concepts" and "applications"). If you are an experienced functional programmer, you will see instances early in the book where a lambda expression here, or eta-conversion there, will simplify things, but I have chosen to delay such simplifications in most cases. Flooding the student with too many features early on can be overwhelming.

The only exception to following the given chapter order is that Chapters 20 to 22 provide a somewhat independent thread on computer music, and can be covered anytime after Chapter 11. The most difficult chapter is probably Chapter 15, and the most dispensible chapters are probably Chapters 17 and 22. Also, if you want to omit nonmultimedia applications you might consider skipping Chapter 6, although that chapter contains the first introduction to infinite lists. Finally, Chapters 23 and 24 are short "tours" of the PreludeList Module and Standard Type Classes, respectively, and could be assigned as auxiliary reading, or covered piecemeal as related topics are introduced.

The web page http://www.cs.yale.edu/homes/hudak/SOE contains a great deal of useful information related to the text, including libraries, source code for each chapter, PowerPoint slides, and errata. You can send email to me at paul.hudak@yale.edu with feedback, questions, corrections, etc.

There are several good implementations of Haskell, all available free on the Internet through the Haskell home page at http://haskell.org. One that I especially recommend is the Hugs implementation, a very easy-to-use and easy-to-install Haskell interpreter. Hugs runs on a variety of platforms, including PC's (Windows 95/NT), various flavors of Unix (Linux, Solaris, HP), and Mac OS. The Glasgow Haskell Compiler (GHC) supports the same libraries as Hugs, and has the benefit of being a true compiler instead of an interpreter.

All of the code in the book is compliant with the Haskell '98 standard, and has been tested on the Hugs '98 implementation of Haskell. Unfortunately, the graphics and animation applications rely on a library that was originally developed only for Windows 95/NT. You should consult the SOE web page for the latest information regarding compatibility with other platforms.

I learned that writing a textbook is not an easy task, and could not have been accomplished without the help of many friends and colleagues. I would especially like to thank Mark Jones, with whom I started this project, and who first suggested the use of the name School of Expression. I'd also like to thank John Peterson and Joe Fasel for help in writing A Gentle Introduction to Haskell (Hudak and Fasel, 1992), from which some of this text was adapted; Alastair Reid for help with the Hugs implementation and graphics libraries; Conal Elliott for many helpful suggestions and inspirations, especially concerning graphics and animation; Erik Meijer for feedback from using a previous version of this text in his class; Mark Tullsen for careful proofreading and tedious index generation; Tom Makucevich and John Garvin for help with computer music; Tim Sheard for feedback from using my book in teaching a functional programming course at Yale, and for creating great PowerPoint slides in the process; Zhanyong Wan for excellent feedback on the text as a Teaching Assistant in Tim's course; Sigbjorn Finne for writing the kaleidoscope program; Valery Trifonov for adapting the kaleidoscope program and other useful feedback; Linda Joyce for help with the indexing and excellent administrative support; Martin Sulzmann for help debugging graphics; Lauren Cowles, my editor, whose patience is extraordinary; and the many students in various classes at Yale who endured earlier versions of the text.

I would also like to thank the several United States funding agencies, most notably NSF and DARPA, who have provided considerable financial support for functional programming research at Yale and elsewhere.

Most of all, this work could not have been accomplished without the love and support of my family. Thank you Cathy, Cristina, and Jennifer.


Happy Haskell Hacking!

Paul Hudak
New Haven
June 1999