Computer LaboratoryIntroduction to Functional Programming

# Introduction to Functional Programming2005-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.

•  © 2006 Dr Marcelo Fiore (content) & Dr Neil Dodgson (layout) Please send any comments to pagemaster@cl.cam.ac.uk Page last updated on 21-Feb-2006 at 10:22 by Marcelo Fiore