Introduction to Functional Programming

Functional programming is a style of programming in which the primary method of computation is the application of functions to arguments. The aim of this course is to review some of the basics of functional programming, using the modern functional language Haskell. The course comprises ten mini-lectures, each with exercises, and concludes with an extended programming example:

1. Introduction (what is functional programming, why is it useful, this course);

2. The Hugs system (what is hugs, the standard prelude, function application, my first script);

3. Types and classes I (what is a type, types in Haskell, basic types, list types, tuple types, function types);

4. Types and classes II (curried functions, curry conventions, polymorphic types, overloaded types, classes in Haskell);

5. Defining functions (conditional expressions, guarded equations, pattern matching, list patterns, lambda expressions, why are lambda useful);

6. List comprehensions (set comprehensions, list comprehensions, dependant generators, guards);

7. Recursive functions (recursive functions, why is recursion useful, recursion on lists, quicksort);

8. Higher-order functions (why are they useful, the map function, the filter function, the foldr function, why is foldr useful);

9. Interactive programs (the problem, the solution, primitive actions, sequencing actions, other library actions, example);

10. Defining types (data declarations, recursive types, arithmetic expressions)

11. The countdown problem (what is countdown, rules, evaluating expressions, specifying the problem, brute force implementation, correctness theorem, how fast is it, can we do better, applying program fusion, how fast is it now, can we do better, exploiting properties, how fast is it now, further work).

This course was prepared for the Summer School on Advanced Functional Programming held in Oxford during August 2002. The slides are available in powerpoint and PDF formats.