Functional Programming: 2009-2010
Information
|
Lecturer |
|
|
Degrees |
Moderations — Honour School of Computer Science |
|
Term |
Michaelmas Term 2009 (16 lectures) |
Overview
This is a first course in programming. It makes use of a programming language called Haskell, in which programs can be viewed as mathematical functions. This makes the language very powerful, so that we can easily construct programs that would be difficult or very large in other languages.An important theme of the course is how to apply mathematical reasoning to programs, so as to prove that a program performs its task correctly, or to derive it by algebraic manipulation from a simpler but less efficient program for the same problem.
The course provides hands-on experience of programming through two lab exercises: the first one aims to make you acquainted with the mechanics of writing Haskell programs, and the second one tackles a more challenging programming task.
Mathematics students taking this course should note that the practical exercises are a compulsory part of the course and will be assessed.
Learning outcomes
At the end of the course the student will be able to:
- Write programs in a functional style;
- Reason formally about functional programs;
- Use polymorphism and higher-order functions;
- Reason about the time and space complexity of programs.
Synopsis
- Programming with a functional notation: sessions and scripts, expressions and values. Evaluation of expressions. Reduction strategies: innermost vs outermost. Functional application and currying. Functional composition.
- Types and strong-typing. Basic types: Booleans and truth values. Simple programs involving pattern matching. Polymorphism and type classes. More types: characters, strings, tuples. Type synonyms
- Lists and their operations; list comprehensions. The functions map, foldl, foldr, concat and filter. Many small examples illustrating the use of these functions in a compositional style of programming.
- Recursion and induction. The algebraic properties of list functions and their proof by equational reasoning. Simple manipulation of programs to achieve efficiency.
- Infinite lists and their applications: Pascal's triangle, digits of a number, sieve of Eratosthesnes. Infinite lists as limits. Proving properties of infinite lists: induction, take lemma.
- Non-linear data structures. Binary trees and the relationship between size and depth. Binary search trees for representing sets. Insertion and searching in a binary search tree.
- Time complexity. Asymptotic notation. Advice on writing efficient programs; use of accumulating parameters.
- Arithmetic expressions: representing, evaluating and manipulating arithmetic expressions. Building a simple parser.
Syllabus
Principles of functional programming: expressions, evaluations, functions, and types. Type definitions and built-in types: numbers, characters, strings and lists. Basic operations on lists, including map, fold and filter, together with their algebraic properties. Recursive definitions and structural induction. Simple program calculation. Infinite lists and their uses. Further data structures: binary trees, general trees. Use of trees for representing sets and symbolic data. Normal order reduction and lazy evaluation. Simple cost models for functional programs; time and space complexity.Reading list
Course text:- Richard Bird, Introduction to Functional Programming using Haskell, second edition, Prentice-Hall International, 1998.
- Graham Hutton, Programming in Haskell, Cambridge University Press, 2007
- Simon Thompson, Haskell: The Craft of Functional Programming, Addison-Wesley, 1996.
- Paul Hudak, The Haskell School of Expression, Cambridge University Press, 2000.