# Introduction to Functional Programming2007–08

Principal lecturer: Dr Marcelo Fiore
Taken by: Part II (General), Diploma
Syllabus
Past exam questions

Lecture slides (lectures I-X)

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