The subject category of Hutton’s excellent, authoritative, yet relatively brief book is functional programming. Section 1.4, “Historical Background,” traces functional programming (and Haskell in particular), from Church and Curry’s 1930s to 1950s notions of functional abstraction and application, to the present, citing the contributions of McCarthy (Lisp), Landin (ISWIM), Backus (function programming (FP)), Milner (Metalanguage (ML)), Turner (Miranda), and the designers of Haskell. Hutton is internationally recognized as a substantial contributor to the Haskell project.

The book is indeed “ideal for beginners ... [as] all concepts are explained from first principles with the aid of carefully chosen examples.” The introductory example of Hoare’s legendary, recursive Quicksort (qsort) demonstrates how natural and to-the-point Haskell and functional programming are. In procedural languages, it is at best the pseudocode (if it exists) that makes this recursive algorithm understandable, though still with some red-herring, distracting variables. Hutton’s use of the Dijkstra-Scholten proof format, wherein each succeeding step of the proof chain is preceded by a rationale, is one of the book’s (many) best features:

The 13 chapters and two appendices cover, in addition to introductory, historical, and general matter, the Hugs and Glasgow facilities for creating and running Haskell programs, including Haskell’s Standard Prelude; types and classes, including lists, tuples, functions, and polymorphic and overloaded types; function definitions, including lambda expressions, conditional expressions, guarded equations, currying, and sections; list and string comprehension, and creating and deciphering the Caesar cipher as a very good list processing example; and recursion (a particular strength of Haskell), including multiple and mutual recursion, as well as quite comprehensible tips on optimizing the performance of recursive functions. On the subject of recursion, Hutton also mentions the very important motivation for including recursion (to be elaborated in a subsequent chapter):“Defining functions using recursion also allows properties of those functions to be proved using the powerful technique of induction.”

Though Haskell’s expressive power with minimal means comes through on every page of this very enlightening book, I single out chapter 7, “Higher-order Functions,” as showing us the useful elegance and “mind-friendliness” that is enabled by the fundamental fold-right (the composition of a list of functions) and fold-left (foldr, foldl) functions. Higher-order functions are where Haskell and functional programming really come into their own. The rare person whose first programming experience is functional programming will not realize what a brave new world Haskell and its ilk comprise. The section in chapter 7 on the transmission of strings that are encoded as bit-strings, a practical example of the power of higher-order functions, will, I daresay, elicit enthusiasm (and relief) in even the most inveterate procedural and assembly language bit twiddlers.

Chapters 8, 9, and 11, though continuing to deal in fundamentals, are also quite applied in nature: “Parsers,” “Interactive Programming,” and “The Countdown Problem,” with the last addressing the construction of numeric expressions that satisfy certain constraints. “Parsers” demonstrates how Haskell enables, in my words, easy tree programming. Chapter 10, on types and classes, elaborates on these all-important concepts, showing how the “data” mechanism enables recursive types. The tautology-checker and abstract machine examples are excellent pedagogical tools. (I’ve written at least one of each, in C++ and B respectively, and marvel at Haskell’s power and cognitive efficiency.)

Chapter 12 is a by no means lazy explication of lazy evaluation, with a definition that is ultra clear: “the use of call-by-name evaluation in conjunction with sharing [common expressions].” A fundamental rationale for designing Haskell to evaluate functions lazily is that Haskell allows computation with infinite structures. This makes Haskell a consummate theoretical tool (in addition to its practicality). The closing of the theory-practice gap is aided by Haskell’s rendering, via lazy evaluation, infinities as potential infinities, a bonus and comfort to us constructivist-intuitionist sympathizers. The Haskell version of the Sieve of Eratosthenes (for generating all prime numbers) is worth the proverbial thousand words. Hutton states: “Being able to separate control from data is one of the most important [further] benefits of lazy evaluation.”

Chapter 13, the final chapter, is titled “Reasoning about Programs.” The underlying mechanism for Haskell is equational reasoning, one of several mathematically equivalent forms of deductive techniques available to computing scientists. Giving excellent examples of this type of reasoning, Hutton also elaborates induction on numbers and induction on lists. Although “reasoning about functional programs is a subject for a book in its own right,” according to Hutton, he nevertheless shows the power of mathematics in “the development of efficient programs with simple proofs.”

This book is highly recommended as an excellent introduction to functional programming.