Hutton - Programming in Haskell

Programming in Haskell

Haskell is one of the leading languages for teaching functional programming, enabling students to write simpler and cleaner code, and to learn how to structure and reason about programs.

This introduction is ideal for beginners: it requires no previous programming experience and all concepts are explained from first principles with the aid of carefully chosen examples. Each chapter includes a series of exercises, ranging from the straightforward to extended projects, along with suggestions for further reading on more advanced topics. The presentation is clear and simple, and benefits from having been refined and class-tested over several years.

Features:

Powerpoint slides for each chapter freely available for instructors and students from the books website

Solutions to exercises, and examination questions (with solutions) available to instructors

All the code in the book is fully compliant with the latest release of Haskell, and can be downloaded from the web.

Written by a leading Haskell researcher and instructor, well known for his teaching skills

Can be used with courses, or as a stand-alone text for self-learning

Graham Hutton has worked in four of the leading centres for research and teaching on functional programming. He has more than 15 years of experience in functional programming research, during which time he has published more than 30 research articles, chaired the Haskell Workshop, and edited a special issue on Haskell of the Journal of Functional Programming. He also has more than 10 years experience in teaching Haskell, and in promoting the use of functional programming in the curriculum.

Programming in Haskell

Graham Hutton

University of Nottingham

CAMBRIDGE UNIVERSITY PRESS

Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, So Paulo, Delhi, Mexico City

Cambridge University Press

The Edinburgh Building, Cambridge CB2 8RU, UK

Published in the United States of America by Cambridge University Press, New York

www.cambridge.org

Information on this title: www.cambridge.org/9780521692694

G. Hutton 2007

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

8th printing 2012

Printed and bound by MPG Books Group, UK

A catalogue record for this publication is available from the British Library

Library of Congress Cataloguing in Publication data

ISBN 978-0-521-87172-3 Hardback

ISBN 978-0-521-69269-4 Paperback

Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate. Information regarding prices, travel timetables and other factual information given in this work are correct at the time of first printing but Cambridge University Press does not guarantee the accuracy of such information thereafter.

For Annette, Callum and Tom

Contents

Preface

there are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.

Tony Hoare, 1980 ACM Turing Award Lecture

This book is about an approach to programming in which simplicity, clarity, and elegance are the key goals. More specifically, it is an introduction to the functional style of programming, using the language Haskell.

The functional style is quite different to that promoted by most current languages, such as Java, C++, C, and Visual Basic. In particular, most current languages are closely linked to the underlying hardware, in the sense that programming is based upon the idea of changing stored values. In contrast, Haskell promotes a more abstract style of programming, based upon the idea of applying functions to arguments. As we shall see, moving to this higher-level leads to considerably simpler programs, and supports a number of powerful new ways to structure and reason about programs.

The book is primarily aimed at students studying computing science at university level, but is also appropriate for a broader spectrum of readers who would like to learn about programming in Haskell. No previous programming experience is required or assumed, and all the concepts are explained from first principles, with the aid of carefully chosen examples.

The version of Haskell used in the book is Haskell 98, the standard version of the language, for which the recently published definition is the culmination of fifteen years of work by its designers. As this is an introductory text, we do not attempt to cover all aspects of Haskell and its associated libraries. Around half of the book is dedicated to introducing the main features of the language, while the other half comprises examples and case studies of programming of Haskell. Each chapter includes a series of exercises, and suggestions for further reading on more advanced and specialist topics.

The book is based upon course material that has been refined and class-tested over many years at the University of Nottingham. Most of the material from the book can be covered in twenty hours of lectures, supported by approximately forty hours of private study, practical sessions in a supervised laboratory, and take-home programming courseworks. However, additional time would be required to cover some of the later chapters in more detail, along with some of the later programming examples.

The website for the book provides a range of supporting material, including Powerpoint slides for each chapter, and Haskell code for each of the extended examples. Instructors can also obtain model answers to the exercises for each chapter, together with a large collection of exam questions and their model answers, by emailing solutions@cambridge.org.

Acknowledgements

The Foundations of Programming group at the University of Nottingham is an excellent environment in which to do research and teaching on functional programming. I am grateful to the University for providing a sabbatical to start work on this book; all the students and tutors on my Haskell courses for their feedback; and Thorsten Altenkirch, Neil Ghani, Mark Jones (now at Portland State), Conor McBride, and Henrik Nilsson in the FOP group for our many discussions about functional ideas and how to present them.

I would also like to thank David Tranah and Dawn Preston for their editorial work at Cambridge University Press; Mark Jones for the Hugs interpreter for Haskell; Ralf Hinze and Andres Lh for the lhs2TeX system for typesetting Haskell; Rik van Geldrop and Jaap van der Woude for their feedback on using drafts of the book; Kees van den Broek, Frank Heitmann, and Bill Tonkin for pointing out errors; Ian Bayley and the anonymous reviewers for useful comments; and Joel Wright for timing the countdown programs.

Graham Hutton

Nottingham, 2006

chapter 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 history, and conclude with two small examples that give a taste of Haskell.