Learning Haskell and Advanced Functional Programming

Motivation for Using Haskell

• Why Functional Programming Matters by John Hughes, The Computer Journal, Vol. 32, No. 2, 1989, pp. 98 - 107. Also in: David A. Turner (ed.): Research Topics in Functional Programming, Addison-Wesley, 1990, pp. 17 - 42.
  Exposes the advantages of functional programming languages. Demonstrates how higher-order functions and lazy evaluation enable new forms of modularization of programs.

• Higher-order + Polymorphic = Reusable by Simon Thompson. Unpublished, May 1997.
  Abstract: This paper explores how certain ideas in object oriented languages have their correspondents in functional languages. In particular we look at the analogue of the iterators of the C++ standard template library. We also give an example of the use of constructor classes which feature in Haskell 1.3 and Gofer.

Using Monads

• Monadic I/O in Haskell 1.3 by Andrew Gordon and Kevin Hammond.
  Abstract: We describe the design and use of monadic I/O in Haskell 1.3, the latest revision of the lazy functional programming language Haskell. Haskell 1.3 standardises the monadic I/O mechanisms now available in many Haskell systems. The new facilities allow fairly sophisticated text-based application programs to be written portably in Haskell. The standard provides implementors with a flexible framework for extending Haskell to incorporate new language features. Apart from the use of monads, the main advances over the previous standard are: character I/O based on handles (analogous to ANSI C file pointers), an error handling mechanism, terminal interrupt handling and a POSIX interface. Apart from a tutorial description of the new facilities we include a worked example: a derived monad for combinator parsing.
• Monads Made Easy by Ahmed Hammad
  From the Introduction: This paper is designed to help others who want to know about Monads, but don't want an overly technical explanation. Here I explain the basics, what monads are, what they are good for, and how to employ them. I do this by writing a simple exception handling system in Haskell using these features.
• How to Declare an Imperative by Philip Wadler, International Logic Programming Symposium '95, MIT Press, 1995. An extended version will appear in ACM Computing Surveys.
  Abstract: This tutorial describes the use of a monad to integrate interaction into a purely declarative language. This technique has been implemented in the higher-order functional language Haskell. A sketch is given of how it might be added to a first-order language for logic programming.
• Monads for functional programming by Philip Wadler, Marktoberdorf Summer School on Program Design Calculi, Springer Verlag, NATO ASI Series F: Computer and systems sciences, Volume 118, August 1992.
  Abstract: The use of monads to structure functional programs is described. Monads provide a convenient framework for simulating effects found in other languages, such as global state, exception handling, output, or non-determinism. Three case studies are looked at in detail: how monads ease the modification of a simple evaluator; how monads act as the basis of a datatype of arrays subject to in-place update; and how monads can be used to build parsers.
• Combining monads by Philip Wadler, Glasgow Workshop on Functional Programming, Springer Verlag Workshops in Computing Series, Ayr, July 1992.
  Abstract: Monads provide a way of structuring functional programs. Most real applications require a combination of primitive monads. Here we describe how some monads may be combined with others to yield a combined monad.
• Monadic Parser Combinators by Graham Huttonand Erik Meijer, Technical report NOTTCS-TR-96-4, Department of Computer Science, University of Nottingham, 1996. A condensed version of this report will appear as a functional pearl in JFP.
  Besides being a tutorial on parser combinators it is also an introduction to monads in general.

Data Structures

Collections

• Bulk types with class by Simon Peyton Jones, (electronic) proceedings of the 1996 Glasgow Functional Programming Workshop.
  Abstract: Bulk types - such as lists, bags, sets, finite maps, and priority queues - are ubiquitous in programming. Yet many languages don't support them well, even though they have received a great deal of attention, especially from the database community. Haskell is currently among the culprits. This paper has two aims: to identify some of the technical difficulties, and to attempt to address them using Haskell's constructor classes.

List-like data structures

• Functional Data Structures by Chris Okasaki. Advanced Functional Programming, Second International Summer School on Advanced Functional Programming Techniques, Evergreen State College, WA, USA, LNCS 1126, 1996 (editors: J. Launchbury, E. Meijer, T. Sheard), p. 131-158.
• Purely Functional Random-Access Lists by Chris Okasaki. Functional Programming Languages and Computer Architecutre, June 1995, pages 86-95.
• Simple and Efficient Purely Functional Queues and Deques by Chris Okasaki. Journal of Functional Programming, 5(4):583-592, October 1995.
• Optimal Purely Functional Priority Queues by Gerth Stølting Brodal and Chris Okasaki, Journal of Functional Programming, 6(6), December 1996.

Graphs

• Graph Algorithms with a Functional Flavour by John Launchbury, Advanced Functional Programming, First International Spring School on Advanced Functional Programming Techniques, Bastad, Sweden, LNCS 925,p. 308-331, 1995 (editors: J. Jeuring, E. Meijer).
• Structuring Depth First Search Algorithms in Haskell by David King and John Launchbury. Proc. ACM Principles of Programming Languages, San Francisco, 1995.
  Abstract: Depth-first search is the key to a wide variety of graph algorithms. In this paper we express depth-first search in a lazy functional language, obtaining a linear-time implementation. Unlike traditional imperative presentations, we use the structuring methods of functional languages to construct algorithms from individual reusable components. This style of algorithm construction turns out to be quite amenable to formal proof, which we exemplify through a calculational-style proof of a far from obvious strongly-connected components algorithm.

Others

• Sparse matrix representations in a functional language by P.W. Grant, J.A. Sharp, M.F. Webster and X. Zhang, Journal of Functional Programming, 6(1):143-170, January 1996.
  Abstract: This paper investigates several sparse matrix representation schemes and associated algorithms in Haskell for solving linear systems of equations arising from solving realistic computational fluid dynamics problems using a finite element algorithm. This work complements that of Wainwright and Sexton [J. Functional Programming, 2(1):61-72, 1992] in that a Choleski direct solver (with an emphasis on its forward/backward substitution steps) is examined. Experimental evidence comparing time and space efficiency of these matrix representation schemes is reported, together with associated forward/backward substitution implementations. Our results are in general agreement with Wainwright and Sexton's.

Parser Combinators

• How to Replace Failure by a List of Successes by Philip Wadler, Functional Programming Languages and Computer Architecture, LNCS 201, 1985.
• Higher-order functions for parsing by Graham Hutton, J. Functional Programming 2(3):323-343, 1992.
• Monadic Parser Combinators by Graham Huttonand Erik Meijer, Technical report NOTTCS-TR-96-4, Department of Computer Science, University of Nottingham, 1996. A condensed version of this report will appear as a functional pearl in JFP.
  Besides being a tutorial on parser combinators it is also an introduction to monads in general.
• Functional Parsers by Jeroen Fokker, First International Spring School on Advanced Functional Programming Techniques, LNCS 925, 1995.
• Predictive parser combinators need four values to report errors by Andrew Partridge, David Wright, J. Functional Programming 6(2): 355-364, 1996.
• Combinators for parsing expressions by Steve Hill, J. Functional Programming 6(3):445-463, May 1996.
• Deterministic, Error-Correcting Combinator Parsers by S. Doaitse Swierstra and Luc Duponcheel, Second International Summer School on Advanced Functional Programming Techniques, LNCS 1126, 1996.

Teaching Haskell

• Where do I begin? A problem solving approach to teaching functional programming by Simon Thompson. In Krzysztof Apt, Pieter Hartel, and Paul Klint, editors, First International Conference on Declarative Programming Languages in Education. Springer-Verlag, September 1997.
  Abstract: This paper introduces a problem solving method for teaching functional programming, based on Polya's `How To Solve It', an introductory investigation of mathematical method. We first present the language independent version, and then show in particular how it applies to the development of programs in Haskell. The method is illustrated by a sequence of examples and a larger case study.
• Functional programming through the curriculum by Simon Thompsonand Steve Hill. In Pieter H. Hartel and Rinus Plasmeijer, editors, Functional Programming Languages in Education, LNCS 1022, pages 85-102. Springer-Verlag, December 1995.
  Abstract: This paper discusses our experience in using a functional language in topics across the computer science curriculum. After examining the arguments for taking a functional approach, we look in detail at four case studies from different areas: programming language semantics, machine architectures, graphics and formal languages.

Proving Program Correctness

• Formulating Haskell by Simon Thompson. Technical Report 29-92*, University of Kent, Computing Laboratory, University of Kent, Canterbury, UK, November 1992.
  Abstract: The functional programming language Haskell is examined from the point of view of proving programs correct. Particular features explored include the data type definition facilities, classes, the behaviour of patterns and guards and the monad approach to IO in the Glasgow Haskell compiler.

Schools on Advanced Funtional Programming

• Advanced Functional Programming, First International Spring School on Advanced Functional Programming Techniques, Bastad, Sweden, LNCS 925, 1995 (editors: J. Jeuring, E. Meijer).
  • Functional Parsers by Jeroen Fokker, p. 1-23.
  • Monads for functional programming by Philip Wadler, p. 24-52.
  • The Design of a Pretty-printing Library by John Hughes, p. 52-96.
  • Functional Programming with Overloading and Higher-Order Polymorphism, Mark P. Jones, p. 97-136.
  • Programming with Fudgets by Thomas Hallgren and Magnus Carlsson, p. 137-182.
  • Constructing Medium Sized Efficient Functional Programs in Clean by Marko C.J.D. van Eekelen and Rinus J. Plasmeijer, p. 183-227.
  • Merging Monads and Folds for Functional Programming by Erik Meijer and Johan Jeuring, p. 228-266.
  • Programming with Algebras by Richard B. Kieburtz and Jeffrey Lewis, p. 267-307.
  • Graph Algorithms with a Functional Flavour by John Launchbury, p. 308-331.
• Advanced Functional Programming, Second International Summer School on Advanced Functional Programming Techniques, Evergreen State College, WA, USA, LNCS 1126, 1996 (editors: J. Launchbury, E. Meijer, T. Sheard).
  • Composing the User Interface with Haggis by Sigbjorn Finne and Simon Peyton Jones, p. 1-37.
  • Haskore Music Tutorial by Paul Hudak, p. 38-67.
  • Polytypic Programming by Johan Jeuring and Patrick Jansson, p. 68-114.
  • Implementing Threads in Standard ML by Peter Lee, p. 115-130.
  • Functional Data Structures by Chris Okasaki, p. 131-158.
  • Heap Profiling for Space Efficiency by Colin Runciman and Niklas Röjemo, p. 159-183.
  • Deterministic, Error-Correcting Combinator Parsers by S. Doaitse Swierstra and Luc Duponcheel, p. 184-207.
  • Essentials of Standard ML Modules by Mads Tofte, p. 208-238.

Links

• Functional Programming by Jeffrey A. Meunier
  Abstract: This report provides a survey of the current state of the art in the field of functional programming, from a beginner's viewpoint. A comparison of functional programming and imperative programming is made, several implementations of functional programming are reviewed, and the concept of time-dependent planning is looked at and how functional programming relates to it.
• Collection of teaching material for functional programming
• John Hughes' collection of tutorial papers in functional programming
• The SEL-HPC Functional Programming Archive