Haskell - Définition
La liste des auteurs de cet article est disponible ici.
Introduction
| Haskell | |
| |
| Auteur | le comité Haskell |
|---|---|
| Développeurs | la communauté Haskell |
| Paradigmes | fonctionnel |
| Typage | Fort, statique |
| Dialectes | Helium, O'Haskell, Template Haskell, PolyP |
| Influencé par | Lisp et Scheme, ISWIM, FP, APL, Hope, SISAL, Miranda, ML, Lazy ML, Orwell, Alfl, Id, Ponder |
| Implémentations | GHC, Hugs, Yhc, |
| Système d'exploitation | Multiplate-forme |
| Site Web | http://www.haskell.org |
Haskell est un langage de programmation fonctionnel. Il est fondé sur le lambda-calcul et la logique combinatoire. Son nom vient du mathématicien et logicien Haskell Brooks Curry. Il a été créé en 1985. Le dernier standard semi-officiel est Haskell 98 : c'est une version minimale et portable du langage conçue à des fins pédagogiques et comme base de futures extensions. Le langage continue d'évoluer rapidement, avec Hugs et GHC (voir ci-dessous), constituant ainsi le standard de facto.
Les fonctionnalités les plus intéressantes de Haskell sont le support des fonctions récursives, l'inférence de types, les listes en compréhension et l'évaluation paresseuse. Ces fonctionnalités, surtout si on les combine, facilitent l'écriture des fonctions. Haskell se distingue également par l'utilisation de monades pour les entrées/sorties.
En 2002, c'est probablement le langage fonctionnel sur lequel le plus de recherches ont été entreprises. Plusieurs variantes ont été développées. Des versions parallélisées faites au Laboratory for Computer Science du Massachusetts Institute of Technology (MIT) et à l'Université de Glasgow ont toutes deux été appelées Parallel Haskell. Des versions plus parallélisées et plus distribuées sont appelées Distributed Haskell (anciennement Goffin) et Eden. Une version d'exécution spéculative, Eager Haskell et plusieurs versions orientées objets, Haskell++, O'Haskell et Mondrian ont vu le jour.
Il existe aussi d'autres langages similaires à Haskell :
- le Concurrent Clean, qui offre un support pour la création de GUI ainsi que CAL (Quarks Framework) qui tourne sur VM Java et est prévu pour s'intégrer comme extension d'API Java.
- une version éducative de Haskell, appelée Gofer, a été développée par Mark Jones, et a finalement été supplantée par HUGS, le Système Gofer de l'Utilisateur Haskell (Haskell User's Gofer System).
Exemples de code
Fonction factorielle (récursive)
La définition classique de la fonction factorielle :
-
fac 0 = 1
-
fac n = n * fac (n - 1)
Fonction factorielle (avec product)
La définition élégante de la fonction factorielle (qui utilise la fonction Haskell product et la notation sur les listes) :
fac n = product [1..n]
Fonction Fibonacci (naïve)
Une implémentation naïve de la fonction qui retourne le n-ième nombre de la suite de Fibonacci :
-
fib 0 = 0
-
fib 1 = 1
-
fib n = fib (n - 2) + fib (n - 1)
Fonction Fibonacci (seconde version)
Une fonction qui retourne la liste des nombres de Fibonacci :
fibs = 0: 1: (zipWith (+) fibs (tail fibs))
La valeur précédente est une liste infinie, ce qui est tout à fait possible grâce à l'évaluation paresseuse. Grâce à cette liste, on peut implémenter fib de cette manière :
fib n = fibs !! n
(!! est un opérateur qui retourne le n-ième élément d'une liste).
Comme fibs est évalué de manière paresseuse dans fib, un appel à fib n ne provoque que l'évaluation des n premiers termes de fibs. Cette évaluation se fait en temps linéaire. Finalement, fib retourne le n-ième terme de la suite de Fibonacci en temps linéaire.
Tri rapide (quicksort)
L'algorithme du tri rapide peut être élégamment écrit en Haskell avec l'aide de la manipulation de listes :
-
qsort [] = []
-
qsort (x:xs) =
-
qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
-
where -
elts_lt_x = [y | y <- xs, y < x]
-
elts_greq_x = [y | y <- xs, y >= x]
Ou
-
qsort [] = []
-
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
Notez qu'à cause des nombreuses copies et concaténations de listes, ce code peut être vraiment lent, en fonction de l'implémentation.
