Programming in Haskell (Graham Hutton) (Z-Library)

📄 File Format: PDF

💾 File Size: 3.8 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

(This page has no text content)

📄 Page 2

Programming in Haskell Second Edition Haskell is a purely functional language that allows programmers to rapidly develop clear, concise and correct software. The language has grown in popularity in recent years, both in teaching and in industry. This book is based on the author’s experience of teaching Haskell for more than 20 years. All concepts are explained from first principles and no programming experience is required, making this book accessible to a broad spectrum of readers. While Part I focuses on basic concepts, Part II introduces the reader to more advanced topics. This new edition has been extensively updated and expanded to include recent and more advanced features of Haskell, new examples and exercises, selected solutions, and freely downloadable lecture slides and code. The presentation is clean and simple, while also being fully compliant with the latest version of the language, including recent changes concerning applicative, monadic, foldable and traversable types. GRAHAM HUTTON is Professor of Computer Science at the University of Nottingham. He has taught Haskell to thousands of students and received numerous best lecturer awards. Hutton has served as an editor of the Journal of Functional Programming, chair of the Haskell Symposium and the International Conference on Functional Programming, vice-chair of the ACM Special Interest Group on Programming Languages, and he is an ACM Distinguished Scientist.

📄 Page 3

Programming in Haskell Second Edition GRAHAM HUTTON University of Nottingham

📄 Page 4

University Printing House, Cambridge CB2 8BS, United Kingdom One Liberty Plaza, 20th Floor, New York, NY 10006, USA 477 Williamstown Road, Port Melbourne, VIC 3207, Australia 4843/24, 2nd Floor, Ansari Road, Daryaganj, Delhi - 110002, India 79 Anson Road, #06-04/06, Singapore 079906 Cambridge University Press is part of the University of Cambridge. It furthers the University’s mission by disseminating knowledge in the pursuit of education, learning, and research at the highest international levels of excellence. www.cambridge.org Information on this title: www.cambridge.org/9781316626221 10.1017/9781316784099 © Graham Hutton 2007, 2016 This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published 2007 Second edition 2016 Printed in the United Kingdom by Clays, St Ives plc in 2016 A catalogue record for this publication is available from the British Library ISBN 978-1-316-62622-1 Paperback Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third-party Internet Web sites referred to in this publication, and does not guarantee that any content on such Web sites is, or will remain, accurate or appropriate.

📄 Page 5

For Annette, Callum and Tom

📄 Page 6

Contents Foreword Preface Part I Basic Concepts 1 Introduction 1.1 Functions 1.2 Functional programming 1.3 Features of Haskell 1.4 Historical background 1.5 A taste of Haskell 1.6 Chapter remarks 1.7 Exercises 2 First steps 2.1 Glasgow Haskell Compiler 2.2 Installing and starting 2.3 Standard prelude 2.4 Function application 2.5 Haskell scripts 2.6 Chapter remarks 2.7 Exercises 3 Types and classes 3.1 Basic concepts 3.2 Basic types 3.3 List types 3.4 Tuple types 3.5 Function types 3.6 Curried functions 3.7 Polymorphic types 3.8 Overloaded types 3.9 Basic classes 3.10 Chapter remarks 3.11 Exercises

📄 Page 7

4 Defining functions 4.1 New from old 4.2 Conditional expressions 4.3 Guarded equations 4.4 Pattern matching 4.5 Lambda expressions 4.6 Operator sections 4.7 Chapter remarks 4.8 Exercises 5 List comprehensions 5.1 Basic concepts 5.2 Guards 5.3 The zip function 5.4 String comprehensions 5.5 The Caesar cipher 5.6 Chapter remarks 5.7 Exercises 6 Recursive functions 6.1 Basic concepts 6.2 Recursion on lists 6.3 Multiple arguments 6.4 Multiple recursion 6.5 Mutual recursion 6.6 Advice on recursion 6.7 Chapter remarks 6.8 Exercises 7 Higher-order functions 7.1 Basic concepts 7.2 Processing lists 7.3 The foldr function 7.4 The foldl function 7.5 The composition operator 7.6 Binary string transmitter 7.7 Voting algorithms 7.8 Chapter remarks 7.9 Exercises 8 Declaring types and classes

📄 Page 8

8.1 Type declarations 8.2 Data declarations 8.3 Newtype declarations 8.4 Recursive types 8.5 Class and instance declarations 8.6 Tautology checker 8.7 Abstract machine 8.8 Chapter remarks 8.9 Exercises 9 The countdown problem 9.1 Introduction 9.2 Arithmetic operators 9.3 Numeric expressions 9.4 Combinatorial functions 9.5 Formalising the problem 9.6 Brute force solution 9.7 Performance testing 9.8 Combining generation and evaluation 9.9 Exploiting algebraic properties 9.10 Chapter remarks 9.11 Exercises Part II Going Further 10 Interactive programming 10.1 The problem 10.2 The solution 10.3 Basic actions 10.4 Sequencing 10.5 Derived primitives 10.6 Hangman 10.7 Nim 10.8 Life 10.9 Chapter remarks 10.10 Exercises 11 Unbeatable tic-tac-toe 11.1 Introduction 11.2 Basic declarations

📄 Page 9

11.3 Grid utilities 11.4 Displaying a grid 11.5 Making a move 11.6 Reading a number 11.7 Human vs human 11.8 Game trees 11.9 Pruning the tree 11.10 Minimax algorithm 11.11 Human vs computer 11.12 Chapter remarks 11.13 Exercises 12 Monads and more 12.1 Functors 12.2 Applicatives 12.3 Monads 12.4 Chapter remarks 12.5 Exercises 13 Monadic parsing 13.1 What is a parser? 13.2 Parsers as functions 13.3 Basic definitions 13.4 Sequencing parsers 13.5 Making choices 13.6 Derived primitives 13.7 Handling spacing 13.8 Arithmetic expressions 13.9 Calculator 13.10 Chapter remarks 13.11 Exercises 14 Foldables and friends 14.1 Monoids 14.2 Foldables 14.3 Traversables 14.4 Chapter remarks 14.5 Exercises 15 Lazy evaluation 15.1 Introduction

📄 Page 10

15.2 Evaluation strategies 15.3 Termination 15.4 Number of reductions 15.5 Infinite structures 15.6 Modular programming 15.7 Strict application 15.8 Chapter remarks 15.9 Exercises 16 Reasoning about programs 16.1 Equational reasoning 16.2 Reasoning about Haskell 16.3 Simple examples 16.4 Induction on numbers 16.5 Induction on lists 16.6 Making append vanish 16.7 Compiler correctness 16.8 Chapter remarks 16.9 Exercises 17 Calculating compilers 17.1 Introduction 17.2 Syntax and semantics 17.3 Adding a stack 17.4 Adding a continuation 17.5 Defunctionalising 17.6 Combining the steps 17.7 Chapter remarks 17.8 Exercises Appendix A Selected solutions A.1 Introduction A.2 First steps A.3 Types and classes A.4 Defining functions A.5 List comprehensions A.6 Recursive functions A.7 Higher-order functions A.8 Declaring types and classes A.9 The countdown problem A.10 Interactive programming

📄 Page 11

A.11 Unbeatable tic-tac-toe A.12 Monads and more A.13 Monadic parsing A.14 Foldables and friends A.15 Lazy evaluation A.16 Reasoning about programs A.17 Calculating compilers Appendix B Standard prelude B.1 Basic classes B.2 Booleans B.3 Characters B.4 Strings B.5 Numbers B.6 Tuples B.7 Maybe B.8 Lists B.9 Functions B.10 Input/output B.11 Functors B.12 Applicatives B.13 Monads B.14 Alternatives B.15 MonadPlus B.16 Monoids B.17 Foldables B.18 Traversables Bibliography Index

📄 Page 12

Foreword It is nearly a century ago that Alonzo Church introduced the lambda calculus, and over half a century ago that John McCarthy introduced Lisp, the world’s second oldest programming language and the first functional language based on the lambda calculus. By now, every major programming language including JavaScript, C++, Swift, Python, PHP, Visual Basic, Java, ... has support for lambda expressions or anonymous higher-order functions. As with any idea that becomes mainstream, inevitably the underlying foundations and principles get watered down or forgotten. Lisp allowed mutation, yet today many confuse functions as first-class citizens with immutability. At the same time, other effects such as exceptions, reflection, communication with the outside world, and concurrency go unmentioned. Adding recursion in the form of feedback-loops to pure combinational circuits lets us implement mutable state via flip-flops. Similarly, using one effect such as concurrency or input/output we can simulate other effects such as mutability. John Hughes famously stated in his classic paper Why Functional Programming Matters that we cannot make a language more powerful by eliminating features. To that, we add that often we cannot even make a language less powerful by removing features. In this book, Graham demonstrates convincingly that the true value of functional programming lies in leveraging first-class functions to achieve compositionality and equational reasoning. Or in Graham’s own words, “functional programming can be viewed as a style of programming in which the basic method of computation is the application of functions to arguments”. These functions do not necessarily have to be pure or statically typed in order to realise the simplicity, elegance, and conciseness of expression that we get from the functional style. While you can code like a functional hacker in a plethora of languages, a semantically pure and lazy, and syntactically lean and terse language such as Haskell is still the best way to learn how to think like a fundamentalist. Based upon decades of teaching experience, and backed by an impressive stream of research papers, in this book Graham gently guides us through the whole gambit of key functional programming concepts such as higher-order functions, recursion, list comprehensions, algebraic datatypes and pattern matching. The book does not shy away from more advanced concepts. If you are still confused by the n-th blog post that attempts to explain monads, you are in the right place. Gently starting with the IO monad, Graham progresses from functors to applicatives using many concrete examples. By the time he arrives at monads, every reader will feel that they themselves could have come up with the concept of a monad as a generic pattern for composing functions with effects. The chapter on monadic parsers brings everything together in a compelling use-case of parsing arithmetic expressions in the implementation of a simple calculator. This new edition not only adds many more concrete examples of concepts introduced throughout the book, it also introduces the novel Haskell concepts of foldable and traversable types. Readers familiar with object-oriented languages routinely use iterables and visitors to enumerate over all values in a container, or respectively to traverse complex data structures. Haskell’s higher-kinded type classes allow for a very concise and abstract treatment of these concepts by means of the Foldable and Traversable classes. Last but not least, the final chapters of the book give an in-depth overview of lazy evaluation and equational reasoning to prove and derive programs. The capstone chapter on calculating compilers especially appeals to me because it touches a topic that has had my keen interest for many decades, ever since my own PhD thesis on the same topic.

📄 Page 13

While there are plenty of alternative textbooks on Haskell in particular and functional programming in general, Graham’s book is unique amongst all of these in that it uses Haskell simply as a tool for thought, and never attempts to sell Haskell or functional programming as a silver bullet that magically solves all programming problems. It focuses on elegant and concise expression of intent and thus makes a strong case of how pure and lazy functional programming is an intelligible medium for efficiently reasoning about algorithms at a high level of abstraction. The skills you acquire by studying this book will make you a much better programmer no matter what language you use to actually program in. In the past decade, using the first edition of this book I have taught many tens of thousands of students how to juggle with code. With this new edition, I am looking forward to extending this streak for at least another 10 years. Erik Meijer

📄 Page 14

Preface What is this book? Haskell is a purely functional language that allows programmers to rapidly develop software that is clear, concise and correct. The book is aimed at a broad spectrum of readers who are interested in learning the language, including professional programmers, university students and high-school students. However, no programming experience is required or assumed, and all concepts are explained from first principles with the aid of carefully chosen examples and exercises. Most of the material in the book should be accessible to anyone over the age of around sixteen with a reasonable aptitude for scientific ideas. How is it structured? The book is divided into two parts. Part I introduces the basic concepts of pure programming in Haskell and is structured around the core features of the language, such as types, functions, list comprehensions, recursion and higher-order functions. Part II covers impure programming and a range of more advanced topics, such as monads, parsing, foldable types, lazy evaluation and reasoning about programs. The book contains many extended programming examples, and each chapter includes suggestions for further reading and a series of exercises. The appendices provide solutions to selected exercises, and a summary of some of the most commonly used definitions from the Haskell standard prelude. What is its approach? The book aims to teach the key concepts of Haskell in a clean and simple manner. As this is a textbook rather than a reference manual we do not attempt to cover all aspects of the language and its libraries, and we sometimes choose to define functions from first principles rather than using library functions. As the book progresses the level of generality that is used is gradually increased. For example, in the beginning most of the functions that are used are specialised to simple types, and later on we see how many functions can be generalised to larger classes of types by exploiting particular features of Haskell. How should it be read? The basic material in part I can potentially be worked through fairly quickly, particularly for those with some prior programming experience, but additional time and effort may be required to absorb some of material in part II. Readers are recommended to work through all the material in part I, and then select appropriate material from part II depending on their own interests. It is vital to write Haskell code for yourself as you go along, as you can’t learn to program just by reading. Try out the examples from each chapter as you proceed, and solve the exercises for each chapter before checking the solutions. What’s new in this edition?

📄 Page 15

The book is an extensively revised and expanded version of the first edition. It has been extended with new chapters that cover more advanced aspects of Haskell, new examples and exercises to further reinforce the concepts being introduced, and solutions to selected exercises. The remaining material has been completely reworked in response to changes in the language and feedback from readers. The new edition uses the Glasgow Haskell Compiler (GHC), and is fully compatible with the latest version of the language, including recent changes concerning applicative, monadic, foldable and traversable types. How can it be used for teaching? An introductory course might cover all of part I and a few selected topics from part II; my first-year course covers chapters 1–9, 10 and 15. An advanced course might start with a refresher of part I, and cover a selection of more advanced topics from part II; my second-year course focuses on chapters 12 and 16, and is taught interactively on the board. The website for the book provides a range of supporting materials, including PowerPoint slides and Haskell code for the extended examples. Instructors can obtain a large collection of exams and solutions based on material in the book from solutions@cambridge.org. Acknowledgements I am grateful to the University of Nottingham for providing a sabbatical to produce this new edition; Thorsten Altenkirch, Venanzio Capretta, Henrik Nilsson and other members of the FP lab for our many enjoyable discussions; Iván Pérez Domínguez for useful comments on a number of chapters; the students and tutors on all of my Haskell courses for their feedback; Clare Dennison, David Tranah and Abigail Walkington at CUP for their editorial work; the GHC team for producing such a great compiler; and finally, Catherine and Ian Hutton for getting me started in computing all those years ago. Many thanks also to Ki Yung Ahn, Bob Davison, Philip Hölzenspies and Neil Mitchell for providing detailed comments on the first edition, and to the following for pointing our errors and typos: Paul Brown, Sergio Queiroz de Medeiros, David Duke, Robert Fabian, Ben Fleis, Robert Furber, Andrew Kish, Tomoyas Kobayashi, Florian Larysch, Carlos Oroz, Douglas Philips, Bruce Turner, Gregor Ulm, Marco Valtorta and Kazu Yamamoto. All of these comments have been taken into account when preparing the new edition. Graham Hutton

📄 Page 16

Part I Basic Concepts

📄 Page 17

1 Introduction In this chapter we set the stage for the rest of the book. We start by reviewing the notion of a function, then introduce the concept of functional programming, summarise the main features of Haskell and its historical background, and conclude with three small examples that give a taste of Haskell. 1.1 Functions In Haskell, a function is a mapping that takes one or more arguments and produces a single result, and is defined using an equation that gives a name for the function, a name for each of its arguments, and a body that specifies how the result can be calculated in terms of the arguments. For example, a function double that takes a number x as its argument, and produces the result x + x, can be defined by the following equation: double x = x + x When a function is applied to actual arguments, the result is obtained by substituting these arguments into the body of the function in place of the argument names. This process may immediately produce a result that cannot be further simplified, such as a number. More commonly, however, the result will be an expression containing other function applications, which must then be processed in the same way to produce the final result. For example, the result of the application double 3 of the function double to the number 3 can be determined by the following calculation, in which each step is explained by a short comment in curly parentheses: double 3 = { applying double } 3 + 3 = { applying + } 6 Similarly, the result of the nested application double (double 2) in which the function double is applied twice can be calculated as follows: double (double 2) = { applying the inner double } double (2 + 2) = { applying + } double 4 = { applying double } 4 + 4 = { applying + } 8 Alternatively, the same result can also be calculated by starting with the outer application of the function double rather than the inner: double (double 2)

📄 Page 18

= { applying the outer double } double 2 + double 2 = { applying the first double } (2 + 2) + double 2 = { applying the first + } 4 + double 2 = { applying double } 4 + (2 + 2) = { applying the second + } 4 + 4 = { applying + } 8 However, this approach requires two more steps than our original version, because the expression double 2 is duplicated in the first step and hence simplified twice. In general, the order in which functions are applied in a calculation does not affect the value of the final result, but it may affect the number of steps required, and whether the calculation process terminates. These issues are explored in more detail when we consider how expressions are evaluated in chapter 15. 1.2 Functional programming What is functional programming? Opinions differ, and it is difficult to give a precise definition. Generally speaking, however, functional programming can be viewed as a style of programming in which the basic method of computation is the application of functions to arguments. In turn, a functional programming language is one that supports and encourages the functional style. To illustrate these ideas, let us consider the task of computing the sum of the integers (whole numbers) between one and some larger number n. In many current programming languages, this would normally be achieved using two integer variables whose values can be changed over time by means of the assignment operator =, with one such variable used to accumulate the total, and the other used to count from 1 to n. For example, in Java the following program computes the required sum using this approach: int total = 0; for (int count = 1; count <= n; count++) total = total + count; That is, we first initialise an integer variable total to zero, and then enter a loop that ranges an integer variable count from 1 to n, adding the current value of the counter to the total each time round the loop. In the above program, the basic method of computation is changing stored values, in the sense that executing the program results in a sequence of assignments. For example, the case of n = 5 gives the following sequence, in which the final value assigned to the variable total is the required sum: total = 0; count = 1; total = 1; count = 2; total = 3; count = 3; total = 6; count = 4; total = 10; count = 5;

📄 Page 19

total = 15; In general, programming languages such as Java in which the basic method of computation is changing stored values are called imperative languages, because programs in such languages are constructed from imperative instructions that specify precisely how the computation should proceed. Now let us consider computing the sum of the numbers between one and n using Haskell. This would normally be achieved using two library functions, one called [..] that is used to produce the list of numbers between 1 and n, and the other called sum that is used to produce the sum of this list: sum [1..n] In this program, the basic method of computation is applying functions to arguments, in the sense that executing the program results in a sequence of applications. For example, the case of n = 5 gives the following sequence, in which the final value in the sequence is the required sum: sum [1..5] = { applying [..] } sum [1,2,3,4,5] = { applying sum } 1 + 2 + 3 + 4 + 5 = { applying + } 15 Most imperative languages provide some form of support for programming with functions, so the Haskell program sum [1..n] could be translated into such languages. However, many imperative languages do not encourage programming in the functional style. For example, many such languages discourage or prohibit functions from being stored in data structures such as lists, from constructing intermediate structures such as the list of numbers in the above example, from taking functions as arguments or producing functions as results, or from being defined in terms of themselves. In contrast, Haskell imposes no such restrictions on how functions can be used, and provides a range of features to make programming with functions both simple and powerful. 1.3 Features of Haskell For reference, the main features of Haskell are listed below, along with particular chapters of this book that give further details. Concise programs (chapters 2 and chapters 4) Due to the high-level nature of the functional style, programs written in Haskell are often much more concise than programs written in other languages, as illustrated by the example in the previous section. Moreover, the syntax of Haskell has been designed with concise programs in mind, in particular by having few keywords, and by allowing indentation to be used to indicate the structure of programs. Although it is difficult to make an objective comparison, Haskell programs are often between two and ten times shorter than programs written in other languages. Powerful type system (chapters 3 and chapters 8) Most modern programming languages include some form of type system to detect incompatibility errors, such as erroneously attempting to add a number and a character. Haskell has a type system that usually requires little type information from the programmer, but allows a large class of

📄 Page 20

incompatibility errors in programs to be automatically detected prior to their execution, using a sophisticated process called type inference. The Haskell type system is also more powerful than most languages, supporting very general forms of polymorphism and overloading, and providing a wide range of special purpose features concerning types. List comprehensions (chapter 5) One of the most common ways to structure and manipulate data in computing is using lists of values. To this end, Haskell provides lists as a basic concept in the language, together with a simple but powerful comprehension notation that constructs new lists by selecting and filtering elements from one or more existing lists. Using the comprehension notation allows many common functions on lists to be defined in a clear and concise manner, without the need for explicit recursion. Recursive functions (chapter 6) Most programs involve some form of looping. In Haskell, the basic mechanism by which looping is achieved is through recursive functions that are defined in terms of themselves. It can take some time to get used to recursion, particularly for those with experience of programming in other styles. But as we shall see, many computations have a simple and natural definition in terms of recursive functions, especially when pattern matching and guards are used to separate different cases into different equations. Higher-order functions (chapter 7) Haskell is a higher-order functional language, which means that functions can freely take functions as arguments and produce functions as results. Using higher-order functions allows common programming patterns, such as composing two functions, to be defined as functions within the language itself. More generally, higher-order functions can be used to define domain- specific languages within Haskell itself, such as for list processing, interactive programming, and parsing. Effectful functions (chapters 10 and chapters 12) Functions in Haskell are pure functions that take all their inputs as arguments and produce all their outputs as results. However, many programs require some formof side effect that would appear to be at odds with purity, such as reading input from the keyboard, or writing output to the screen, while the program is running. Haskell provides a uniform framework for programming with effects, without compromising the purity of functions, based upon the use of monads and applicatives. Generic functions (chapters 12 and chapters 14) Most languages allow functions to be defined that are generic over a range of simple types, such as different forms of numbers. However, the Haskell type system also supports functions that are generic over much richer kinds of structures. For example, the language provides a range of library functions that can be used with any type that is functorial, applicative, monadic, foldable, or traversable, and moreover, allows new structures and generic functions over them to be defined. Lazy evaluation (chapter 15) Haskell programs are executed using a technique called lazy evaluation, which is based upon the idea that no computation should be performed until its result is actually required. As well as avoiding unnecessary computation, lazy evaluation ensures that programs terminate whenever