Functional Programming Skip to main content University of Oxford Department of Computer Science Search for Search Toggle Main Menu Home Admissions Research News & Events About Us Alumni Our Students (current) Innovation Home Our Students Courses Functional Programming Functional Programming: 2021-2022 Lecturer Geraint Jones Degrees Preliminary Examinations — Computer Science and Philosophy Preliminary Examinations — Computer Science Preliminary Examinations — Mathematics and Computer Science Term Michaelmas Term 2021 (16 lectures) Overview The lectures for this course will be pre-recorded and available on Panopto (click Recorded Lectures>2021-22>Functional Programming). The lectures will be supported by discussion sessions live on Teams. 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. Learning outcomes At the end of the course the student will be able to: Write programs in a functional style; Reason formally about functional programs; Use polymorphism and higher-order functions; Reason about the time and space complexity of programs. Synopsis Programming by writing functions: expressions, values, types, evaluation. Function definitions in Haskell scripts, interactive sessions. Mathematical functions as programs, function application as program execution; lists for sequencing, and function composition as a program structuring tool. Strong typing. Basic types, constructed types (sums and products); constructors, selectors, and discriminators; definitions by pattern matching. Parametric polymorphism, type classes and ad-hoc polymorphism; recursive types. Lists, finite and infinite lists; list comprehensions, standard list functions including map, filter, concat. Evaluation as computation, evaluation order; recursive definitions, non-termination and an outline of the idea of computability. Sorting as an example; the concept of efficiency of evaluation, and the asymptotic complexity of a calculation. Sudoku solver as an example; the idea of infeasibly inefficient algorithms. Proofs by induction. The take lemma, induction on finite lists, induction on infinite lists. The notion of chain completeness. Folds on data structures. Left- and right- folds on lists. Fold fusion. Standard functions as instances of folds. Scans as folds. Unfolds. Writing programs by solving equations for unknown functions. Efficiency improvement techniques involving accumulating parameters. Associativity and the relationship between left- and right-folds. Log time exponentiation. Countdown as an example. Abstract syntax trees. Tabulation and dynamic programming. Parsers as an example. The idea of parser combinators, as an introduction to monads. The do notation. SyllabusPrinciples 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: Either of Richard Bird, Introduction to Functional Programming using Haskell, second edition, Prentice-Hall International, 1998. Graham Hutton, Programming in Haskell (2nd edition), Cambridge University Press, 2016. Additional Reading: Richard Bird, Thinking Functionally With Haskell, Cambridge University Press, October 2014. Bryan O'Sullivan, Don Stewart, and John Goerzen, Real World Haskell, O'Reilly Media, 2008. Miran Lipovača, Learn You a Haskell for Great Good! A Beginner's Guide, No Starch Press, 2011. Simon Thompson, Haskell: The Craft of Functional Programming, Addison-Wesley, 1996. Paul Hudak, The Haskell School of Expression, Cambridge University Press, 2000. Paul Chiusano and Rúnar Bjarnason, Functional Programming in Scala. Manning Publications Co., 2014. The Haskell standard Prelude Feedback Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome. Our Students Course A-Z Functional Programming Information Timetables Course materials Past exam papers Sample solutions Previous course materials Degrees Online Resources & Handbooks Minerva Examinations Timetables Back to Top Calendars Internal RSS Feeds Sitemap Privacy & Cookies Accessibility Statement © University of Oxford /teaching/courses/2021-2022/fp/index.html
