Generic Programming: Advanced Lectures

Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis, and J. van Leeuwen 2793 3 Berlin Heidelberg New York Hong Kong London Milan Paris Tokyo Roland Backhouse Jeremy Gibbons (Eds.) Generic Programming Advanced Lectures 13 Series Editors Gerhard Goos, Karlsruhe University, Germany Juris Hartmanis, Cornell University, NY, USA Jan van Leeuwen, Utrecht University, The Netherlands Volume Editors Roland Backhouse The University of Nottingham School of Computer Science and Information Technology Jubilee Campus, Wollaton Road, Nottingham NG8 1BB, UK E-mail: [email protected] Jeremy Gibbons Oxford University Computing Laboratory Wolfson Building, Parks Road, Oxford OX1 3QD, UK E-mail: [email protected] Cataloging-in-Publication Data applied for A catalog record for this book is available from the Library of Congress. Bibliographic information published by Die Deutsche Bibliothek Die Deutsche Bibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data is available in the Internet at . CR Subject Classification (1998): D.3, D.1, D.2, F.3, E.1 ISSN 0302-9743 ISBN 3-540-20194-7 Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. Springer-Verlag Berlin Heidelberg New York a member of BertelsmannSpringer Science+Business Media GmbH http://www.springer.de © Springer-Verlag Berlin Heidelberg 2003 Printed in Germany Typesetting: Camera-ready by author, data conversion by Olgun Computergrafik Printed on acid-free paper SPIN: 10931868 06/3142 543210 Preface Generic programming is about making programming more effective by making it more general. This volume is about a novel form of genericity in programs, based on parameterizing programs by the structure of the data they manipulate. The material is based on lectures presented at a summer school on Generic Programming held at the University of Oxford in August 2002. The lectures by Hinze and Jeuring introduced Generic Haskell, an extension of the Haskell programming language that allows the programmer to define a function by induction on the structure of types. The implementation of Generic Haskell provided a valuable tool for students to experiment with applications of this form of datatype genericity. The lecture material in this volume is divided into two parts. The first part (“practice and theory”) introduce