FP

Functional Programming

Objectives

This course is an introduction to the functional programming paradigm. The programming language used is Haskell. This paradigm does not require students to know about the physical architecture of computers allowing to address advanced programming concepts (high order or overloading), as well as the fundamental topics of (functional) programming. Thus, at the end of the course, the student should be able to: ● Solve programming problems by breaking them down into smaller problems; ● Develop recursive list and tree algorithms; ● Develop programs by taking advantage of higher order functions; ● Apply the notion of principal type and polymorphism; ● Define algebraic types, fit them into the class hierarchy and program with those types; ● Write interactive programs

Program

1. Introduction to the functional (programming) paradigm. Basic aspects of the Haskell programming language: values, expressions and types; reduction; type inference: pattern matching; polymorphism.
2. Lists. Recursive definitions of functions over lists. Solving problems using lists
3. List sorting algorithms: insertion sort, merge sort, and quick-sort
4. High order functions: computation patterns.
5. Algebraic data types: definition and use.
6. Trees: binary trees, search trees, rose trees, and corresponding algorithms.
7. The class mechanism and overloading
8. Functional IO: the monad IO.

Bibliography

Main

1. Bird, R. (1998). Introduction to Functional Programming using Haskell. Prentice-Hall.
2. Valença, J. M., Barros, J. B. (1999). Fundamentos da Computação. Livro II: Programação Funcional, Universidade Aberta. Complementary
3. Thompson, S. (2011). Haskell: the Craft of Functional Programming (3rd ed.). Addison-Wesley.
4. Hutton, G. (2016). Programming in Haskell(2nd ed.). Cambridge University Press.