Advanced Functional Programming
Aachen Univ. of Technology,
Dept. of CS,
Lehrstuhl für Informatik II,
Research,
FP,
Haskell
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, AddisonWesley, 1990, pp. 17  42.
Exposes the advantages of functional programming languages.
Demonstrates how higherorder functions and lazy evaluation enable new forms
of modularization of programs.

Higherorder + 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
textbased 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 higherorder functional language Haskell. A
sketch is given of how it might be added to a firstorder 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
nondeterminism. 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 inplace 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 NOTTCSTR964, 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.
Listlike 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. 131158.
 Purely Functional RandomAccess Lists by Chris Okasaki. Functional Programming Languages and Computer Architecutre, June 1995, pages 8695.
 Simple and Efficient Purely Functional Queues and Deques by Chris Okasaki. Journal of Functional Programming, 5(4):583592, 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. 308331, 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:
Depthfirst search is the key to a wide variety of graph algorithms.
In this paper we express depthfirst search in a lazy functional
language, obtaining a lineartime 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 calculationalstyle proof
of a far from obvious stronglyconnected 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):143170, 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):6172, 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.
 Higherorder functions for parsing by Graham Hutton,
J. Functional Programming 2(3):323343, 1992.
 Monadic Parser Combinators by Graham Huttonand Erik Meijer,
Technical report NOTTCSTR964, 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): 355364, 1996.
 Combinators for parsing expressions by Steve Hill,
J. Functional Programming 6(3):445463, May 1996.
 Deterministic, ErrorCorrecting 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. SpringerVerlag, 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 85102. SpringerVerlag, 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 2992*, 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. 123.
 Monads for functional programming by Philip Wadler, p. 2452.
 The Design of a Prettyprinting Library by John Hughes, p. 5296.
 Functional Programming with Overloading and HigherOrder Polymorphism, Mark P. Jones, p. 97136.
 Programming with Fudgets by Thomas Hallgren and Magnus Carlsson, p. 137182.
 Constructing Medium Sized Efficient Functional Programs in Clean by Marko C.J.D. van Eekelen and Rinus J. Plasmeijer, p. 183227.
 Merging Monads and Folds for Functional Programming by Erik Meijer and Johan Jeuring, p. 228266.
 Programming with Algebras by Richard B. Kieburtz and Jeffrey Lewis, p. 267307.
 Graph Algorithms with a Functional Flavour by John Launchbury, p. 308331.
 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. 137.
 Haskore Music Tutorial by Paul Hudak, p. 3867.
 Polytypic Programming by Johan Jeuring and Patrick Jansson, p. 68114.
 Implementing Threads in Standard ML by Peter Lee, p. 115130.
 Functional Data Structures by Chris Okasaki, p. 131158.
 Heap Profiling for Space Efficiency by Colin Runciman and Niklas Röjemo, p. 159183.
 Deterministic, ErrorCorrecting Combinator Parsers by S. Doaitse Swierstra and Luc Duponcheel, p. 184207.
 Essentials of Standard ML Modules by Mads Tofte, p. 208238.
Links
Olaf Chitil,
chitil@i2.informatik.rwthaachen.de,
Last update: August 27th, 1998
