Lecturer	Peter Jeavons
Practical Coordinator	Hanno Nickau
Degrees	Moderations — Computer Science Schedule A — MSc in Advanced Computer Science
Term	Michaelmas Term 2011  (16 lectures)

Overview

MSc students will be assessed by invigilated exam lasting approximately 2 hours in week 0 of HT.

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:

1. Write programs in a functional style;
2. Reason formally about functional programs;
3. Use polymorphism and higher-order functions;
4. 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.

Additional Reading:

• 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.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.