Télecharger cours Haskell: Programmation fonctionnelle

Introduction

Ce document comprend un résumé des notions de base au dessous de la programmation fonctionnelle en utilisant le langage Haskell. Le texte est base sur Introduction to Functional Programming using Haskell de Richard Bird.

Le modele de calcul
L’exécution d’un programme fonctionnel comprend l’évaluation d’une expression. Souvent, il y a un environnement interactif qui permet l’évaluation d’une expression entrée par l’utilisateur (comme c’est le cas avec une machine a calculer). On appelle session le cycle continu d’entrer une expression et de la laisser évaluer. Les expressions contiennent généralement des références aux fonctions pré-définies dans une biblioth`eque ou définies par le programmeur dans un script.
L’évaluation d’une expression comprend la simplification de l’expression `a sa plus simple forme équivalente. Une expression qui ne peut plus être simplifiée est dite d’être en forme canonique. Le processus de simplification comprend l’usage des définitions comme r`egles de ré-écriture : si l’expression `a simplifier est une instance de la partie gauche d’une définition (= pattern matching), elle simplifie a la partie droite de la r`egle sous la substitution appropriée. On appelle réduction.

La définition de fonctions
Reconsidérons la définition de la fonction smaller. Une définition équivalente est sma l l er : : ( Integer , Integer ) − > Integer
sma l l er (x , y)
| x < = y = x
| x > y = y
Cette définition utilise des équations gardées (= guarded equations). Une telle définition comprend plusieurs clauses, séparées par une barre verticale. Chaque clause contient une condition et une expression ; les deux parties sont séparées par le symbole “=”. Il est évident qu’une fonction peut être récursive :
f ac t : : Integer − > Integer
f ac t n
| n == 0 = 1
| n > 0 = n ∗ f ac t (n − 1)

Les types
Haskel est un langage fortement typé (= strongly typed), ce qui implique que l’évaluateur ne veut évaluer que des expressions bien formées. Une expression est bien formée quand on peut déterminer son type en ne considérant que les types des sous-expressions et les signatures des opérations utilisées. Par exemple l’expression quad (3 + 4).

Les types simples

La définition d’un type comprend la description d’un ensemble de valeurs éventuellement infini. Dans ce texte, nous verrons comment les types de base sont définis en Haskell. Il est évident que ces techniques de définition peuvent être utilisées pour introduire de nouveaux types.

Définition par énumération
Une premi`ere méthode pour définir un type dont l’ensemble de valeurs est fini, est d’énumérer explicitement tous les éléments appartenant `a ce type. Le type Bool – comprenant les valeurs logiques – et le type Char – comprenant les caract`eres – sont tous les deux défini par l’énumération explicite de leurs éléments.
Le type booléen
Le type booléen est défini en Haskell comme l’ensemble comprenant les valeurs True et False :
data Bool = False | True
On observe l’usage des majuscules dans le nom du type et de ses valeurs. Ensuite, on peut définir des fonctions qui prennent un argument booléen utilisant “pattern matching” comme dans l’exemple suivant :
not : : Bool − > Bool
not True = False
not False = True
Afin de simplifier une expression de la forme not e, les équations sont utilisées comme des r`egles de ré-écriture. D’abord, e est simplifiée `a sa forme canonique.
Si ce processus se termine et résulte `a True, l’évaluateur appliquera la premiere regle. Si le résultat est False, la deuxi`eme r`egle est utilisée. Si e ne peut pas être réduit `a une forme canonique, la valeur de not e est indéfinie.

…