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
.
