home search a-z help
University of Cambridge Computer Laboratory
Introduction to Functional Programming
Computer Laboratory > Course material 2005-06 > Introduction to Functional Programming

Introduction to Functional Programming
2005-06

Principal lecturer: Dr Marcelo Fiore
Taken by: Part II (General), Diploma

Syllabus
Past exam questions

Lecture slides
  • Introduction
  • Lecture I: functional programming; expressions and values; functions; recursion; types.
  • Lecture II: mosml; sml; value declarations; static binding; basic types (integers, reals, truth values, characters, strings); function declarations; overloading; tuples; recursion; expression evaluation; call-by-value.
  • Lecture III: types; polymorphism; curried functions; nameless functions; lists; pattern matching; case expressions; list manipulation; tail recursion; accumulators; local bindings.
  • Lecture IV: higher-order functions; list functionals.
  • Lecture V: sorting: insertion sort, quick sort, merge sort; parametric sorting; queues; signatures; structures; functors; generic sorting.
    Code: queues, sorting.
  • Lecture VI: records; enumerated types; polymorphic datatypes; option type; disjoint-union type; abstract types; error handling; exceptions.
    Code: complex numbers, abstract queues with error handling by options and by exceptions.
  • Lecture VII: recursive datatypes: lists, trees, lambda calculus; tree manipulation; tree listings: preorder, inorder, postorder; tree exploration: breadth-first and depth-first search; polymorphic exceptions; isomorphisms.
    Code: tree searching,
  • Lecture VIII: tree-based data structures; binary search trees; red/black trees; flexible functional arrays; heaps; priority queues.
    Code: binary search trees, red/black trees, flexible functional arrays, priority-queue heaps.
  • Lecture IX: call-by-value, call-by-name, and call-by-need evaluation; lazy datatypes: sequences, streams, trees; lazy evaluation; sieve of Eratosthenes; breadth-first and depth-first traversals.
    Code: The sieve of Eratosthenes by division and by counting.
  • Lecture X: testing and verification; rigorous and formal proofs; structural induction on lists; law of extensionality; multisets; structural induction on trees.
  • Exercises
  • Exercises on functions and lists.
  • Exercises on lists and trees.
  • Exercises on stuctural induction.
  • Complementary material
  • See Larry Paulson's Foundations of Computer Science course for notes, exercises, and more.
  • Feedback
  • Please provide feedback through the online lecture course feedback form.