In this course, we will study functional programming, and will learn how to take advantage of the features of modern typed functional programming languages. We will study in depth the notions of algebraic data types, higher-order functions, polymorphism, and side-effects. The practice sessions will be done in Haskell, but concepts presented in the course can be applied in many other languages such as OCaml, SML or Python.

Prerequisites: CSE201 and CSE203

Fall 2023 Schedule:

- Lab: Mondays 15h30-17h30
- Lecture: Wednesdays 14h15-15h45

Instructors:

- Noam Zeilberger (email: noam.zeilberger@polytechnique.edu, office: 2052 Alan Turing Building)
- Théo Boury (email: theo.boury@polytechnique.edu)
- Jill-Jênn Vie (only on 4 September)

Your grade is computed based on:

six formative assignments (24% = 6 x 4%)

one assessed in-class exam (20%)

a final project (36%)

participation (20%)

where regularly asking questions during labs or lectures or on the Moodle Q & A forum will earn you full credit for participation. Attendance at labs is mandatory except for medical reasons or with prior permission. Attendance at lectures is strongly encouraged.

The formative assignments are meant purely for learning, and you will receive full credit so long as you make a reasonable attempt at completing them. Collaboration on formative assignments is also allowed and encouraged, although you should understand everything that you submit and acknowledge your collaborators (as well as any online forums or tools such as ChatGPT).

The in-class exam will be during week 6, and will cover a selection of the topics discussed in lectures and labs during weeks 1-5. Note that it will be a paper exam, without access to computers. (More information and sample questions will be provided closer to the date of the exam.)

The final project will be introduced during the last week of the course, due after the holiday break. Working in groups is possible for the final project with prior approval. Each project group will give a brief presentation, scheduled within the first two weeks of November.

The Glasgow Haskell Compiler (GHC) is an open source compiler and interpreter for Haskell. It includes the following programs that may be run from the command line:

`ghci`

: the interpreter. The main way of interacting with the interpreter is to enter Haskell expressions at the`>`

prompt, which will then be evaluated and printed. There are many other more specialized commands; for example, two important ones are`:load`

(or`:l`

) for loading a file, and`:type`

(or`:t`

) to find out the type of an expression.`ghc`

: the compiler. You can use this to produce stand-alone executables from Haskell source.`runghc`

(or`runhaskell`

). This allows you to run Haskell programs*without*having to compile them first.

Documentation on all of these programs and more is available at the GHC User’s Guide.

GHC 9.6.2 is already installed on the lab machines. You can verify this by running

`$ ghc --version`

in a terminal. We will be using the interpreter `ghci`

more often than the compiler `ghc`

. You can run it as follows:

```
$ ghci
GHCi, version 9.6.2: https://www.haskell.org/ghc/ :? for help
Prelude>
```

To install GHC for yourself (e.g., on your laptop), the easiest approach may be to use ghcup. In addition to installing GHC, ghcup will also install the Cabal library manager and build system, and optionally Stack, which is a newer tool for developing Haskell projects.

In any case, make sure that you install a stable release of GHC, version 9.6.2 or higher.

Whereas labs are designed to provide more practical programming experience, lectures cover the theoretical foundations of functional programming. I will attempt to provide lecture notes reasonably in advance of (or eventually after) the lectures, with the understanding that they may not be an exact transcript of what happened during lecture, and that I reserve the right to modify them at any point to incorporate corrections/improvements/additions. I will also post a copy of any slides that I use, eventually incorporating bug fixes. Of course you are welcome to take your own notes during lectures!

Although there is no course textbook, the following books may be helpful to complement the lectures:

Programming in Haskell, 2nd edition by Graham Hutton.

Thinking Functionally with Haskell by Richard Bird.

Copies of both books are available on reserve at the Bibliothèque Centrale. (The book webpage for *Programming in Haskell* also provides links to slides and videos based on Hutton’s Functional Programming course at Nottingham University.)

There are also several good books on Haskell that are freely available online:

Learn you a Haskell for Great Good! A colorful introduction to the language.

Haskell WikiBook. Includes a Beginner’s Track as well as an Advanced Track with lots of more advanced material.

Real World Haskell. Includes extended examples of practical applications.

You may also find these links useful:

- hoogle: like Google but for Haskell.
- Stephen Diehl’s What I wish knew when learning Haskell contains lots of practical tips.

Finally, if you enjoy this course and want to go further, you may be interested in the course INF551 taught by Samuel Mimram, and the associated book.

- 04/09/2022 Lab 1: getting started with Haskell
- 11/09/2022 Lab 2: first-order data types
- 18/09/2022 Lab 3: higher-order functions and type classes
- 25/09/2022 Lab 4: lambda calculus and propositions-as-types
- 02/10/2022 Lab 5: side-effects and monads
- 09/10/2022 Lab 6: laziness and infinite objects
- 16/10/2022 Lab 7: working on the final project

(The schedule of topics is provisional and subject to change.)

- 04/09/2022 Lecture 0: Introduction to functional programming (slides) (notes) (code)
- 06/09/2022 Lecture 1: First-order data types (slides) (notes) (code)
- 13/09/2022 Lecture 2: Higher-order functions and type classes (slides) (notes) (code)
- 20/09/2022 Lecture 3: Lambda calculus and propositions-as-types (slides) (Sections 1-4 and 6-9 of Peter Selinger’s Lecture Notes on the Lambda Calculus) (λ-term visualiser) (haskell code from the end of lecture) (agda version)
- 27/09/2022 Lecture 4: Side-effects and monads (slides) (code)
- 04/10/2022 Lecture 5: Lazy evaluation and infinite objects (slides) (code)
- 11/10/2022 Lecture 6: In-class exam
- 18/10/2022 Lecture 7: Derivatives of data types and zippers (slides) (list zipper code) (Rémy zipper code can be found at the end of the solution set for Lab 5) see also: (Haskell Wikibook on Zippers) (Gérard Huet’s “The Zipper”) (Conor McBride’s “The Derivative of a Regular Type is its Type of One-Hole Contexts”)

This year’s project is about writing a text adventure game on and around trees.