Admin CliCours
Cours pdf et exercices de programmation en Haskell, tutoriel & guide de travaux pratiques en pdf.
C’est un langage fonctionnel typé, de la famille ML (1977 Université St Andrews en Ecosse), inspiré du λ-calcul.
Haskell (1987 en l’honneur de Haskell Curry) est fonctionnel, comme Lisp (1965 Mc Carthy), Scheme et Hope pour des passages par valeur ainsi que Caml (1977 Inria en France), Clean ou Miranda (très analogue à Haskell, 1985 D.Turner), ce qui signifie que l’on déclare pour l’essentiel des fonctions au sens mathématique. Comme Caml, il possède des types de données très rigoureux, et non seulement les contrôle comme dans la plupart des langages, mais les calcule automatiquement, ce qui évite presque toujours au programmeur de les déclarer définissant ses fonctions de la façon abstraite la plus générale possible.
Les points forts de Haskell qui en font un des langages les plus évolués actuellement, sont le caractère purement fonctionnel (y compris les effets de bord), le calcul automatique des types indiquant de plus les contraintes de classe, l’évaluation des paramètres par nécessité (évaluation paresseuse) ce qui permet, entre autre, de donner des définitions mathématiques d’objets infinis, d’autre part, la surcharge de types est mieux prévue pour les opérateurs, on peut donner des définitions par cas avec paramètres structurés un peu comme en Prolog et enfin la syntaxe est nettement moins lourde qu’en Caml, notamment l’analyseur en deux dimensions peut tenir compte de l’indentation.
Définitions de fonctions
La forme générale d’une définition est <nom de fonction> <paramètres> = <corps de la définition>, mais elle peut être définie par cas comme la foction « signe » ci-dessous (attention, sans le =), ou même par plusieurs équations où les paramètres sont structurés de façon à filtrer les différents cas. A ce propos, le joker _ désigne comme en Caml et Prolog un objet quelconque, on pourrait redéfinir head (x : _) = x et tail (_ : q) = q. L’analyseur Haskell est « à deux dimensions », ce qui signifie qu’en indentant correctement les cas, le séparateur ; et les délimiteurs { } deviennent facultatifs.
signe x | x > 0 = 1
| x < 0 = -1
| x == 0 = 0
Currification
Les fonctions ne sont définies qu’à une seule variable. Par exemple (sauf si on donne explicitement l’unique variable comme un couple), une fonction de deux arguments n’est jamais qu’une fonction à un argument (le premier) dont le résultat est lui-même une fonction à un argument (le second). Ainsi si f est (E*F -> G) alors (Curry f) sera (E -> (F -> G)) et en Haskell comme en Caml, l’écriture f x y z inférera que f est de type (E -> (F -> (G -> H))) et cette expression sera prise pour ((f x) y) z avec (f x) de type F -> (G -> h)) et ((f x) y de type (G -> H). On adopte la convention du parenthèsage à gauche, c’est à dire que f g x signifie (f g) x et est interprété. Ainsi une fonction (a -> b) -> (c -> d) peut s’écrire (a -> b) -> c -> d. Une fonction currifiée reçoit donc ses arguments un à un, mais aussi elles sont appliquables partiellement et plus rapides (des constructions de n-uplets en moins) et privilégiées par la compilation.
Récursivité terminale
La récursivité terminale est établie dans le calcul d’une fonction f si et seulement si dans tout appel de f avec certaines valeurs, le résultat final sera celui d’un autre appel (avec d’autres valeurs). Cela signifie que le second appel ayant achevé son travail, le premier n’a pas à reprendre la main pour un travail quelconque supplémentaire comme par exemple la composition avec une autre fonction, il a « terminé ». L’intérêt de la récursivité terminale pour les langages qui la détectent, c’est que chaque sous-programme (un appel de fonction) n’a pas à conserver son contexte lorsqu’il est dérouté sur l’appel suivant puisqu’il a fini et que les valeurs des arguments qu’on lui a passé n’ont plus d’utilité. L’occupation de la mémoire est alors constante comme dans le cas d’un programme itératif.
Une programmation récursive terminale est visible à l’oeil nu dans f(x) = si <condition> alors <valeur> sinon f(…), elle est récursive non terminale dans f(x) = si … alors … sinon g(f(…)) puisque le second appel doit être composé avec un traitement supplémentaire g.
Dans la pratique, on prend tous les paramètres entrant en ligne de compte en cours de résolution du problème, comme fac’ définie pour r (résultat partiellement construit) et n (entier courant descendant de la donnée initiale jusqu’à 1).
…….
Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)Cours et exercices de programmation en Haskell (124 Ko) (Cours PDF)
