Functional programming in OCaml

▸Introduction

Intended for functional beginners already familiar with some programming language.

If all goes well, by the end of this course, you shall be able to:

Understand lambda-terms and write pure functional programs.
Design recursive functions to iterate over recursive data types.
Wonder how you have survived so far without algebraic data types and parameterized types.
Think in terms of higher-order functions in order to write reusable code.
Astonish yourself by writing polymorphic functions without even noticing.

The exam is on october, 23th (to be confirmed): a list of exercises, on computer.

To use OCaml at INSA, copy to your homedir /mnt/commetud/GEI/OCaml/.profile and read it.
Open a new terminal and launch utop: utop
You should get a nice greeting message. Press CTRL+D to quit.
Alternatively, you can write small OCaml programs directly on Try OCaml.

Each lesson must be worked individually, and completed before starting the next one.

An introduction to lambda-calculus.
Facebook's RESCRIPT, or how to program in OCaml while pretending to write Javascript.
Xavier Leroy, proficient developper of the Ocaml compiler, tells how he ran into a bug in some Intel processors.
Watch 👁Tail-call recursion, the musical, which explains how call-stacks work.
Learn why OCaml's Garbage collector is efficient.

Exam questions are only intended to test your skills. They are not intended to be smart or enlightening. Thus, do not get surprised if examples are totally unmeaningful.
You do not have to write tail-recursive functions, unless explicitly required.

The following works only on INSA computers (purposely).

The project is to be done by pairs of students having the same level.

➪ You have completed all the lessons, and know how to write OCaml Modules.

The goal is to implement an algorithm computing the max-flow of a flow graph, using the Ford–Fulkerson algorithm, and optionally improve it to take into account other constraints (e.g. minimize cost).
See the ⮕ details of the project.
You are free to propose another project, by considering another graph algorithm — check with the teacher.

Before ~~december, 15th~~ january, 14th (aoe time), you have to send to your teacher (D. Le Botlan or A. Bit-Monnot) a link to your github project (or any other similar repository).
Manage to meet your teacher and show him a very quick demo (2 minutes). He will then ask you questions about your project (5-10 minutes).

The final grade takes into account:

your achievements (how much is in your project)
your code's modularity (do you use modules, abstract types?)
the level of abstraction and genericity (do you take advantage of polymorphism, parameterized types?)
code quality (comments, conciseness)
your answers to questions during the quick demo

Many resources about OCaml: //ocaml.org/
Books to learn OCaml.
The very official OCaml manual.
A well-written french book about functional programming (Bib'INSA):
Mini Manuel de Programmation Fonctionnelle—Éric Violard—DUNOD 978-2-10-070385-2
OCamlverse : some documentation about OCaml.

See how to install.
The recommended way is OPAM on linux.
Install packages text, utop and ocaml-top.
On windows, see how to install ocaml-top. (Have you considered switching to a decent, free OS ?)

If you need to use a package, e.g. text in an interpreter, you must start your program as follows:
#use "topfind" ;; (* Done once *) #require "text" ;; (* For every package you need. *)

Sequence: when writing a sequence, do not put a ; on the last statement.
let f () = Printf.printf "Meet" ; Printf.printf "John" ; Printf.printf "Doe" ; let g x = x + 1 (* Error detected here. *) let h x = x - 1
- An error is detected at the end of the definition of g.
- It is difficult to understand why the error appears there (try to find out).
- The real error is the extra ; at the end of f (after "Doe").
To avoid this problem, always finish a sequence with unit (and no semicolumn), in order to mark clearly the end of the sequence:
let f () = Printf.printf "Meet" ; Printf.printf "John" ; Printf.printf "Doe" ; () let g x = x + 1 (* No error. *) let h x = x - 1
Nested pattern-matching: be careful when a match occurs inside another pattern-matching:
(* This (curried) function expects two arguments. *) let f x = function | 0 -> false | 1 -> match x with | 0 -> false | 1 -> true | 2 -> true | _ -> false
It does not behave as you think. If you auto-indent the code, you get the real meaning:
let f x = function | 0 -> false | 1 -> match x with | 0 -> false | 1 -> true | 2 -> true | _ -> false
To fix it, use begin...end or parentheses:
let f x = function | 0 -> false | 1 -> begin match x with | 0 -> false | 1 -> true end | 2 -> true | _ -> false
When a match is nested in another pattern-matching, it is good practice to put begin...end around it.

❯ contact.lebotlan ❅ insa-toulouse.fr ❮