Introduction à la programmation en caml

Caml est le langage fonctionnel dans lequel nous allons implémenter les algorithmes de ce module.

Lancement d’ocaml

Comme lua (et contrairement à java), ocaml dispose d’un interpréteur dans lequel nous pouvons directement écrire et tester nos programmes.

Sous linux, nous pouvons taper ocaml dans le terminal. Sous Mac OSX, /opt/local/bin/ocaml. Sous windows on utilisera l’environnement ocaml. Note, sous linux et Mac OSX, pour plus de confort (historique des commandes tapées, utilisation des flèches…), nous préfixerons la commande de rlwrap. Nous obtenons un prompt composé d’un # (qu’il ne faudra pas recopier dans les exemples).

ehainry@backus07% rlwrap ocaml
        Objective Caml version 3.12.1

# 

Pour demander l’évaluation d’une entrée, il faut utiliser ;;

# 12;;
- : int = 12
# 12.5
  ;;
- : float = 12.5
# 

Ici, les lignes commençant par un - sont les réponses de l’interpréteur. On remarque que celui-ci a typé les nombres que nous lui avons donnés.

Pour travailler, nous écrirons les expressions et fonctions dans un éditeur de texte (gedit, textwrangler, scite…) puis nous copie-collerons dans l’interpréteur. L’extension standard des fichiers caml est .ml.

Constructions de base

• Affectations simples de la forme let identifiant = valeur;;, affectations multiples avec and :

  # let x = 1;;
  val x : int = 1
  # let y = 1+2 and z = 7+1;;
  val y : int = 3
  val z : int = 8

• Opérateurs

  • pour les entiers : + - * / mod
  • pour les réels : +. -. *. /.
  • pour les booléens : not and or

  # 17 / 3;;
  - : int = 5
  # 17 mod 3;;
  - : int = 2
  # 17. /. 3.;;
  - : float = 5.66666666666666696
  # 17. +. 3;;
  Error: This expression has type int but an expression was expected of type float
  # not (true or false);;
  - : bool = false

• Conditionnelles et boucles : il n’y en a pas (pour l’instant). Nous les remplacerons par le filtrage et la récursion.

• Fonctions : function x -> x+1 ;;

  • affectation d’une fonction :

    # let f x = x+1 ;;
    val f : int -> int = <fun>

  • appel de la fonction f : f 12

  • filtrage :

    let g x = match x with
    | 0 -> 1
    | n -> 0
    ;;

    Dans cet exemple, la valeur de n ne sert pas, on peut utiliser _ dans la deuxième ligne du filtre qui va accepter n’importe quelle valeur.

  • récursion avec le mot clef rec

    # let rec f n = match n with
    	| 0 -> 1
    	| n -> n + (f (n-1))
    ;;

  • fonction avec des arguments multiples :

    # let add x y = x + y;;
    val add : int -> int -> int = <fun>

  • appel de la fonction : add 1 3.

    Notons que l’on ne considère en fait pas add comme une fonction de deux arguments mais une fonction qui à x associe une fonction qui à y associe x+y. On appelle ce concept la curryfication. Cela impose une façon de parenthéser différente de l’habitude : add (3*7) (4*3) par exemple.

  • add est rigoureusement équivalente à :

    let addition = function x -> (function y -> x+y);;

  • pour filtrer avec des arguments explicites, il faut préciser sur quel argument on filtre (match) :

    # let f x y = match x with
    	| 0 -> y
    	| x -> x
    ;;

  • Évaluation partielle : il est possible de définir une fonction comme l’évaluation d’une autre fonction dont on connaît le ou les premiers arguments :

    # let add1 = add 1;;
    val add1 : int -> int = <fun>
    # add1 7;;
    - : int = 8

  • filtrage sur plusieurs variables :

    # let rec produit x y = match (x, y) with
    	| 0, 0 -> 0
    	| 0, y -> 0
    	| x, 0 -> 0
    	| x, y -> x*y
    ;;

  • filtrage conditionnel : when. Il n’est pas possible de directement filtrer en testant des conditions évoluées, pour cela, on utilise when pour ajouter une condition :

    # let equal x y = match (x, y) with
    	| (0, 0) -> true
    	| (0, y) -> false
    	| (x, y) when x=y -> true
    	| _ -> false
    ;;

Traduction d’une conditionnelle et d’une boucle

Supposons que l’on veuille traduire le code suivant en ocaml :

if a%4==0 then
	print("Bissextile")
else
	print("Pas bissextile")
end

Nous allons utiliser utiliser print_string pour afficher une chaîne de caractères et faire la conditionnelle à l’aide un filtrage de motif :

match a mod 4 = 0 with
| true -> print_string "Bissextile"
| false -> print_string "Pas bissextile"
;;

Si une conditionnelle est déjà dans un filtrage, il pourra être plus intéressant d’utiliser une garde when.

Remarquons que dans le cas proposé ici, les deux branches de la condition utilisent la même fonction appliquée à des arguments différents. On peut donc sortir cette fonction et utiliser le code

print_string (match a mod 4 with
	| 0 -> "Bissextile"
	| _ -> "Pas bissextile"
)
;;

Considérons maintenant à une boucle for.

s = 0
for i=1, 17 do
	s = s + i
end

On peut écrire une fonction récursive prenant i et s et effectuant le corps de la boucle si i est dans le bon intervalle :

let rec boucle i = match i with
| 17 -> i
| i  -> i + (boucle (i+1))
in boucle 1
;;

Enfin pour une boucle while, nous allons utiliser la même idée :

s=1
while s<100 do
	s = s * 2	
end
print(s)

let rec whileloop s = match s<100 with
| true -> whileloop (s*2)
| false -> s
in print_int (whileloop 1)
;;

Néanmoins, traduire ainsi un algorithme sera en général une mauvaise idée. Nous préférerons passer l’algorithme à une version naturellement récursive plutôt.

Exercices

Exercices sur les définitions de fonctions

Listes

La liste permet d’arranger des éléments de même type dans une même structure, de façon ordonnée. C’est le pendant récursif du tableau.

Une liste peut être définie de façon récursive comme pouvant être soit vide, soit constituée d’un premier élément (nommé la tête) et d’une liste des éléments suivants (la queue).

La définition récursive pure est la suivante :

La liste vide [] est une liste.

Si l est une liste et x un élément alors x::l est une liste.

On note :: l’opérateur de construction de liste.

Exemple :

# 1::2::3::[];;
- : int list = [1; 2; 3]

On peut alors filtrer (matcher) sur la forme de la liste :

match l with
| [] -> 1
| t::q -> 0
;;

Exercices

Exercices sur les listes

Piles et files

La pile est une structure de données régie par le principe «Dernier entré, premier sorti» (Last In, First Out ou LIFO en anglais). Elle fonctionne donc comme une pile d’assiette : les nouvelles assiettes sont ajoutées en haut de la pile et quand on a besoin d’une assiette, on la prend en haut de la pile. Comme pour une liste, les éléments sont ordonnés dans la structure, peuvent apparaître de façon multiple et sont rangés linéairement. Cependant, les opérations de base sont légèrement différentes.

Comme pour les listes, une pile peut être vide ou bien constituée d’un sommet posé sur une pile.

On dispose de trois opérations de base pour les piles :

• l’opération empiler qui ajoute un élément au sommet de la pile,
• l’opération depiler qui supprime le sommet de la pile,
• l’opération sommet qui renvoie le sommet de la pile (sans le dépiler).

Nous allons implémenter un nouveau type en caml :

type 'a pile = Vide | E of 'a * 'a pile;;

On dit qu’une pile d’alpha (par exemple une pile d’entiers) est soit la pile vide, soit E(x, p) ou x est un alpha et p une pile d’alpha.

let empiler x p = E(x, p);;
let depiler = function E(x, p) -> p;;
let sommet = function E(x, p) -> x;;

Remarquons que les fonctions depiler et sommet ne traitent pas le cas de la pile vide, il faudra donc faire attention à ne les utiliser que sur des piles non vides.

La file (ou queue) est une structure de données régie par le principe «Premier entré, permier sorti» (First In , First Out ou FIFO en anglais). Elle fonctionne comme une file d’attente : les nouveaux clients sont ajoutés au bout de la queue, il faut être en tête de queue pour accéder au guichet.

Exercices

Exercices sur les piles et les files

Arbres

Exercices

Exercices sur les arbres

Tris

Une utilisation classique des listes nécessite de les trier (disons par ordre croissant). Le tri d’une liste (ou d’un tableau) n’est pas un exercice difficile mais plusieurs méthodes permettent de le réaliser et ces méthodes présentent des complexités différentes.

Nous allons voir et implémenter les algorithmes de tri bulle, le tri sélection, le tri insertion, le tri fusion et le tri par insertion.

Tri bulle

Dans le module d’algorithmique, nous avons vu un algorithme de tri d’un tableau. Il consistait à parcourir le tableau en inversant les éléments si on rencontrait un indice i du tableau tel que t[i] > t[i+1]. L’algorithme s’arrêtait quand le tableau était entièrement trié. Cet algorithme est appelé tri bulle.

function tri (t)
	esttrie = false
	longueur = #t
	while not esttrie do
		esttrie = true
		for i = 1, longueur-1 do
			if t[i] > t[i+1] then
				esttrie = false
				t[i], t[i+1] = t[i+1], t[i]
			end
		end
	end
	return t
end

Du fait de la boucle while, il n’est de calculer la complexité de cet algorithme. Nommons n la longueur du tableau. On remarque qu’à chaque passage dans la boucle while, on parcourt tout le tableau par une boucle for. Cette boucle for a donc une complexité en O(n). On peut se convaincre que l’algorithme termine puisque à chaque itération, le tableau est de mieux en mieux trié (l’inversion supprime un obstacle au tri). On peut aussi se convaincre qu’au bout de n passages dans la boucle while, le tableau sera trié, en effet, après le premier passage, le dernier élément du tableau est nécessairement remonté tout à la fin (comme les bulles dans une boisson gazeuse), après le deuxième passage, les deux derniers éléments du tableau seront les deux plus grands (dans l’ordre), … et après n passages, les n éléments sont dans l’ordre. La complexité au pire est donc en O(n²).

Nous allons maintenant chercher des algorithmes de tri récursifs et de préférence plus efficaces que le tri bulle. Au lieu d’un tableau, nous allons supposer que les éléments sont dans une liste (plus adaptée aux algorithmes récursifs).

Pour une visualisation de chacun de ces algorithmes (y compris le tri-bulle ci-dessus) on pourra étudier les vidéos sur http://www.youtube.com/user/AlgoRythmics/videos. En anglais, le tri bulle est appelé bubble sort, le tri pivot est appelé quick-sort, le tri fusion est appelé merge-sort.

Tri insertion

Étant donnée une liste, soit elle est vide (auquel cas elle est déjà triée). Soit elle est composée d’une tête et d’une queue. Si je suppose la queue triée, il ne reste plus qu’à insérer la tête au bon endroit. Nous allons donc écrire une fonction d’insertion dans une liste triée et la fonction tri_insertion qui réalise le tri :

let rec insertion x liste = match liste with
| [] -> [x]
| t::q -> if t>x
          then x::liste
          else t::(insertion x q)
;;

let rec tri_insertion = function
| [] -> []
| t::q -> insertion t (tri_insertion q)
;;

Tri pivot

Le tri pivot contrairement au tri insertion ne va pas se contenter de réduire le problème d’une unité mais va tenter de fabriquer deux listes de taille moitié, d’appliquer récursivement l’algorithme de tri sur ces listes puis de réassembler les listes. Pour que le réassemblage soit facile, on choisit de prendre comme sous-listes une liste d’éléments inférieurs à un élément choisi que l’on nomme pivot et une liste d’éléments supérieurs à ce pivot. Le réassemblage consistera donc simplement à concaténer la première liste, le pivot puis la deuxième liste.

La partie plus compliquée de cet algorithme va être de constituer les deux listes en question. Le pivot va être choisi comme le premier élément de la liste.

Une fonction separe_aux pivot liste linf lsup va prendre une liste et retourner les listes linf et lsup composées respectivement des éléments inférieurs et des éléments supérieurs au pivot.

La fonction tri_pivot va donc, si la liste n’est pas vide va donc générer les listes linf, lsup = separe_aux pivot liste [] [], trier linf et lsup et les concaténer.

Tri fusion

Le tri fusion part du même constat que le tri pivot : il est plus intéressant de couper la liste en deux listes de même taille que de ne la réduire d’une unité. Cette fois, nous allons vraiment couper en deux listes “égales”, ce qui rendra le réassemblage (la fusion) plus complexe.

Tri par arbre

Nous pouvons utiliser les abr pour réaliser un tri par arbre. L’idée sera d’insérer tous les éléments de la liste dans un abr puis de faire le bon parcours d’arbre pour obtenir la liste des éléments triés.

1. Implémenter le tri par arbre.

Exercices

Exercices sur les tris