Introduction par prof. Anthony A. Aaby

Introduction par prof. Anthony A. Aaby, traduction par Dan V. Popa avec la permission de l'auteur. La traduction doit être vérifiée. La traduction n'est pas encore finie. (Quelques corrections par Chaddaï Fouché)

© 1996 par A. Aaby pour la plus récente version anglaise - Original page used with explicit permision ! You may see it here!

---

Cours d'introduction à Haskell

---

Introduction

Haskell est un langage de programmation fonctionnel, universel, qui porte le nom de Haskell Curry (le logicien). Il a été conçu en 1988 par un comité de 15 membres pour satisfaire, entre d'autres, les contraintes suivantes.

• doit convenir à l'enseignement, à la recherche, et à la programmation de grands systèmes.
• doit être librement disponible.
• est basé sur des idées qui apprécient un consensus large.
• doit réduire la diversité inutile dans des langages de programmation fonctionnels.

Ses particularités incluent fonctions d'ordre supérieur, évaluation non-stricte, fonctions polymorphes, types de données algébriques définis par l'utilisateur, modules , fonctions récursives, fonctions curryfiée (voir curryfication), compréhensions de listes , opération algébriques extensibles et un ensemble riche de types de données primitifs.

La structure d'un programme Haskell

Un module définit une collection de valeurs, de types de données, de synonymes de type, de classes, etc. Le module peut exporter certaines de ces ressources, pour les rendre disponibles à d'autres modules.

Un programme Haskell est une collection de modules, l'un d'entre eux doit par convention s'appeler "Main" et définir une valeur "main" de type "IO ()". Cette fonction main est le point d'entrée du programme (c'est elle qui sera exécutée).

Les modules peuvent référencer d'autres modules par l'intermédiaire de déclarations explicites d'importation (import ...) qui donnent le nom du module à importer, et éventuellement indiquent quelles entités importer, ou s'il faut l'importer qualifié (autrement dit s'il faut répéter le nom du module devant chaque fonction importée de ce module) et sous quel nom. Les modules peuvent être mutuellement récursifs.

Le système d'"inférence de type" signifie qu'il n'est pas nécessaire d'expliciter le type de chaque valeur. Mais Haskell est un tout de même un langage typé statiquement (à la compilation, la cohérence des types est vérifiée) et fortement typé (il n'y a pas de conversion implicite entre les types). Grâce à une syntaxe qui prend en compte l'indentation, il n'est pas nécessaire de terminer chaque définition par un point-virgule ";". On appelle cela le système de "layout" (disposition du code).

Remarque: Pour appliquer une fonction, on sépare simplement la fonction de son argument par des espaces, les parenthèses ne sont pas nécessaires : f x signifie f appliquée à x.

Les commentaires sur une seule ligne sont précédés par « -- » et continuent jusqu'à la fin de la ligne. Par exemple :

   succ n = n + 1  -- cette fonction retourne le successeur de son argument

Les commentaires multilignes commencent par {- et finissent par -}. Ainsi

   {- ceci est
   un commentaire
   multiligne -}

Questions lexicographiques

Il est préférable d'écrire du Haskell avec une police monospace (où tous les symbole on la même largeur comme "Courier New") sous peine de faire des erreurs de layout.

La casse des lettres (majuscule ou minuscule) est significative. De plus, les variables et les variables de types doivent avoir des noms commençant par une minuscule ; les types, les constructeurs, les modules et les classes de types doivent avoir des noms commençant par une majuscule.

Haskell fournit deux méthodes différentes pour écrire des listes de déclarations : soit on les sépare explicitement avec des ";" et on entoure la liste avec des accolades {}, soit on exploite le layout.

Par exemple, au lieu de l'écriture :

 f a + f b where {a = 5 ; b = 4 ; f x = x + 1}

on peut écrire :

 f a + f b 
   where 
     a = 5 ; b = 4
     f X = x + 1

L'application de fonction est curryfiée, associative à gauche et a une priorité plus élevée que n'importe quel opérateur. Ainsi « f x y + g a b » est équivalent à « ((f x) y) + ((g a) b) ». La curryfication est l'opération par laquelle on transforme une fonction à plusieurs arguments en une fonction à un seul argument renvoyant une fonction, exemple :

 f : (x,y) -> x + y

curryfiée, cette fonction devient :

 f : x -> (y -> x + y)

Valeurs et types

Un calcul est l'évaluation d'une expression pour obtenir sa "valeur". Les valeurs sont les membres d'ensembles disjoint appelés "types" --- les nombres entiers (Z), les fonctions, les listes, etc sont tous des valeurs de première classe. Des valeurs de première classe peuvent être passées comme arguments aux fonctions, retournées comme résultat, placées dans des structures de données, etc. Chaque valeur a un type (intuitivement un type est un ensemble de valeurs). Les annotations de type sont des constructions syntactiques qui dénotent des types. Les types ne sont pas de première classe en Haskell.

Les expressions sont des constructions syntactiques qui dénotent des valeurs et ont un type associé.

Types de données prédéfinis

Quelques types de données simples sont prédéfinis : Integer, Int, Float, Double, Bool, and Char.

Les types peuvent être polymorphes, c'est-à-dire ils peuvent contenir des variables de type qui sont universellement quantifiées au-dessus de tous les types. En outre, il est toujours possible d'ajouter une déclaration de type. Les déclarations de type écrites par l'utilisateur sont facultatives.

Types de données structurés prédéfinis

Haskell prévoit de structurer des données par des tuples et des listes {\sl. Les tuples ont la forme :

   (e_1, e_2,…, e_n) n >= 2

Si l'e_i a le type t_i, alors le tuple a le type (t_1, t_2, … , t_n)

Les listes ont la forme : [e_1, e_2, … , e_n] où n >= 0 et chaque élément e_i doit avoir le même type, qu'on appellera t, et le type de la liste est alors [t]. La liste ci-dessus est équivalente à : e_1:e_2:…:e_n:[] ; où «:» est l'opérateur d'infixe représentant «cons».

Types définis pour l'utilisateur Des datatypes définis pour l'utilisateur sont faits par l'intermédiaire d'une déclaration de «données» ayant la forme générale :

   data T u_ 1 … u_n = C_1 t_1,1 … t_1,k_1
   | …
   | C_n t_n,1 … t_n,k_n

où T est un type constructeur ; les u_i sont les "variables" représentant des types ; les c_i sont des constructeurs (de données) ; et le t_i,j sont les types constitutifs (pouvant contenant un certain u_i).

La présence des u_i implique que le type est polymorphe. T peut donc être instancié en substituant les types spécifiques aux u_i.

Voici quelques exemples :

data Bool = True | False
data Color = Red | Green | Blue | Indigo | Violet
data Point a = Pt a a
data Tree a = Branch (Tree a) (Tree a) | Leaf a

Bool et Color sont des constructeurs de type "zéro-aire" parce qu'ils n'ont aucun argument. True, False, Red, etc. sont des constructeurs de données "zéro-aires". Bool et Color sont des énumérations parce que tous leurs constructeurs de données sont "zéro-aire". Point est un produit ou un type constructeur de tuple parce qu'il a seulement un constructeur ; Tree est un type union ; a est souvent appelé un type de données algébrique.

Fonctions

Les fonctions sont de première classe et donc d'ordre supérieur. Elles peuvent être définies par l'intermédiaire des déclarations, ou anonymement par l'intermédiaire des lambda-abstractions. Par exemple,

     \x - > x+1

est une lambda-abstraction et est équivalente à la fonction succ définie par :

   succ x = x + 1

Si x a le type t_1 et exp a le type t_2, alors \x - > exp a le type t_1->t_2. Les définitions de fonction et les abstractions de lambda sont curryfiées, ce qui facilite l'utilisation des fonctions évoluées. Par exemple, considérons cette définition

   add x y = x + y

la fonction succ définie précédemment peut être redéfinie ainsi :

   succ = add 1

La forme curryfiée est utile lorsqu'elle est est utilisée en même temps que la fonction map qui s'applique une fonction à chaque membre d'une liste. Dans ce cas-ci,

   map (add 1) [1, 2, 3] => [2, 3, 4]

map applique la fonction curryfiée add 1 à chaque membre de la liste [1, 2, 3] et renvoie la liste [2, 3, 4].

Des fonctions sont définies en employant une ou plusieurs équations. Pour illustrer la variété de formes que les définitions de fonctions peuvent prendre on peut s'intéresser plusieurs définitions de la fonction factorielle. La première définition est basée sur la définition récursive traditionnelle.

   fac n = if n == 0 then 1 else n * fac (n - 1)

La deuxième définition emploie deux équations et une reconnaissance de motifs sur les arguments pour définir la fonction factorielle.

   fac 0     = 1 
   fac (n+1) = (n+1)*fac(n)

---

Cours d'instruction de Haskell
une autre partie, n'est pas verifie encore
(traduction automatique)

---

La prochaine définition emploie deux équations, l'assortiment de modèle des arguments et utilisations le produit de fonction de bibliothèque qui renvoie le produit des éléments d'une liste. Elle est plus efficace puis la fonction factorielle récursive traditionnelle.

   fac du fac 0 = 1 (n+1) = produit [1. (n+1)]

La définition finale emploie un arrangement plus sophistiqué d'assortiment de modèle et fournit la gestion d'erreur.

   fac n | n < 0 = erreur « entrée dans le fac est négatif » | == 0 = 1 de n | n > 0 = produit [1. .n]

Les opérateurs d'infixe sont des fonctions vraiment justes. Par exemple, l'opérateur de concaténation de liste est défini dans le prélude comme :

   (++) : : [a] - > [a] - > [a] [] ys de ++ = ys (x : ys des xs) ++ = x : (xs++ys)

Puisque les opérateurs d'infixe sont des fonctions justes, ils peuvent être au curry. Des opérateurs au curry s'appellent les sections. Par exemple, les deux premières fonctions additionnent trois et le tiers est employé en passant la fonction d'addition comme paramètre.

   (3+) (+3) (+)

Structure de bloc Elle est également autorisée pour présenter des définitions locales du côté droit d'une définition, au moyen de « où » clause. Considérer par exemple la définition suivante d'une fonction pour résoudre des équations quadratiques (elle échoue ou renvoie une liste d'un ou deux vraies racines) :

   quadsolve un b c | delta < 0 = erreur « racines complexes » | == 0 de delta = [- b (2*a)]                 | delta > 0 = [- b (2*a) + base (2*a), - b (2*a) - base (2*a)]                   là où delta = b*b - delta de la base 4*a*c = du sqrt

La première équation emploie la fonction erreur de builtin, qui cause l'arrêt de programme et l'impression de la corde comme diagnostic.

Là où les clauses peuvent se produire niché, à la profondeur arbitraire, permettant à des programmes de Haskell d'être organisés avec une structure de bloc nichée. L'impression des blocs intérieurs est forcée, car l'information de disposition est employée par l'analyseur. Polymorphisme Les fonctions et les datatypes peuvent être polymorphes ; c.-à-d., universellement mesuré de certaines manières au-dessus de tous les types. Par exemple, le datatype de « arbre » est polymorphe :

   arbre de données a = branche (arbre a) (arbre a) | poussent des feuilles a

Le « arbre interne » est type d'arbres des fixnums ; Le « arbre (char - > Bool) » est le type d'arbres des fonctions traçant des caractères à Booleans, etc. En outre :

   la frange (feuille X) = la frange [x] (branche de gauche à droite) = finge est partie de la droite de frange de ++

la « frange » a le type le « arbre a - > [a] », c.-à-d. ``pour tous dactylographie a, arbres de cartes de frange d'a dans des listes d'A.

Ici

   identification X = ys de x [] ++ = ys (x : ys des xs) ++ = x : carte (xs++ys) f [] = [] carte f (x : xs) = f X : xs de la carte f

l'identification a le type a->a, (++) (apposer) a le type : [a] - > [a] - > [a], et la carte a le type (a->b) - > [a] - > [b]. Ces types sont impliqués automatiquement, mais peuvent sur option être fournis comme type signatures :

   identification : : a - > a (++) : : [a] - > [a] - > carte [a] : : (a->b) - > [a] - > [b]

Dactylographier les synonymes Pour la convenance, Haskell fournit une manière de définir le type synonymes --- c.-à-d. noms pour les types utilisés généralement. Le type synonymes sont créés en utilisant le type déclarations. Les exemples incluent :

   type corde = [type personne de char] = (nom, adresse) type nom = adresse de données de corde = aucun | corde d'Addr

Cette définition de corde fait partie de Haskell, et en fait la syntaxe littérale « bonjour » est sténographie pour :

   [« h », « e », « l », « l », « o »]

Assortiment de modèle Nous avons déjà vu des exemples du modèle-assortiment dans les fonctions (frange, ++, etc.) ; c'est la manière primaire que les éléments d'un datatype sont distingués.

Des fonctions peuvent être définies en donnant plusieurs équations alternatives, si les paramètres formels ont différents modèles. Ceci fournit une autre méthode de faire l'étude de cas qui est souvent plus élégante que l'utilisation des gardes. Nous donnons ici quelques exemples simples de l'assortiment de modèle sur des nombres, des listes, et des tuples normaux. Voici la définition (d'autres) de la fonction factorielle, et une définition de la fonction d'Ackerman :

L'accès des éléments d'un tuple est également fait par l'assortiment de modèle. Par exemple les fonctions de choix sur 2 tuples peuvent être définies ainsi

   fst (a, b) = un snd (a, b) = b

Voici quelques exemples simples des fonctions définies par l'assortiment de modèle sur des listes :

   somme [] = 0 sommes (a : X) = a + produit de la somme X [] = 0 produits (a : X) = a * inverse du produit X [] = [] inverse (a : X) = x renversé ++ [a]

n+k -- les modèles sont utiles en écrivant des définitions inductives au-dessus des nombres entiers. Par exemple :

   ^ de x de X ^ 0 = 1 (n+1) = fac du fac 0 = 1 de x* (x^n) (n+1) = *fac (n+1) n ACK 0 n = n+1 ACK (m+1) 0 = ACK m 1 ACK (m+1) (n+1) = ACK m (ACK (m+1) n)

des Comme-modèles sont employés pour appeler un modèle pour l'usage du côté droit. Par exemple, la fonction qui reproduit le premier élément dans une liste pourrait être écrite comme :

   f (x : xs) = x : X : xs

mais en utilisant un comme-modèle comme suit :

   s@ de f (x : xs) = x : s

Wild-cards. Un match quelque chose de volonté de wild-card et est employé où nous ne nous inquiétons pas quelle certaine partie de l'entrée est. Par exemple :

   tête (x : _) = queue de x (_ : xs) = xs

Expressions de cas L'assortiment de modèle est indiqué dans le rapport en termes d'expressions de cas. Une définition de fonction de la forme :

   f p11… pnk de p1k = d'e1… f pn1… = en

est sémantiquement l'équivalent :

   xk de f x1… = cas (x1,…, xk) de (p11,…, p1k) - > e1… (pn1,…, pnk) - > en

Listes Les listes sont dominantes en Haskell et Haskell fournit un ensemble puissant d'opérateurs de liste. Des listes peuvent être apposées par l'opérateur de « ++ ». L'opérateur « ** » énumère la soustraction. D'autres opérations utiles sur des listes incluent l'opérateur d'infixe « : » qui met en tête un élément à l'avant d'une liste, et de l'infixe « ! ! » ce qui fait l'indiçage. Voici quelques exemples

   [« Lundi », « Tue », « Wed », « Thur », « Fri »] ++ [« reposé », le « soleil »] est [« lundi », « Tue », « Wed », « Thur », « Fri », « reposé », le « soleil »] [1.2.3.4.5] [2.4] est [1.3.5] 0 : [1.2.3] est [0.1.2.3] [0.1.2.3] ! ! 2 est 2

Noter que les listes sont subscripted commencer par 0. La table suivante récapitule les opérateurs de liste.

Symbole Opération X : Liste mettre en tête un élément à une liste Énumérer la liste de ++ enchaîner deux listes Énumérer \ \ liste énumérer la différence Liste ! ! n nième élément d'une liste n = 0. Ordres arithmétiques Il y a une notation de sténographie pour les listes dont les éléments forment une série arithmétique.

   [1..5]    -- rendements [1.2.3.4.5] [1.3..10] -- rendements [1.3.5.7.9]

Dans la deuxième liste, la différence entre les deux premiers éléments est employée pour calculer les éléments restants de la série. Compréhensions de liste Les compréhensions de liste donnent une syntaxe concise pour une classe plutôt générale des itérations au-dessus des listes. La syntaxe est adaptée d'une notation analogue utilisée dans la théorie des ensembles (appelée « placer la compréhension »). Un exemple simple d'une compréhension de liste est :

   [n*n | n < - [1..100]]

C'est une liste contenant (dans l'ordre) les places de tous nombres de 1 à 100. L'expression ci-dessus serait lue à haute voix en tant que « liste de tout le n*n tels que n est tiré de la liste 1 à 100 ». Noter que « n » est une variable locale de l'expression ci-dessus. La construction variable-liante à la droite de la barre s'appelle un « générateur » - « < » signe dénote que la variable présentée sur sa gauche s'étend au-dessus de tous éléments de la liste sur sa droite. La forme générale d'une compréhension de liste en Haskell est :

   [corps | qualificateurs]

là où chaque qualificateur est l'un ou l'autre un générateur, de la forme : variété < - l'exp, ou bien un filtre, qui est une expression booléenne limitait les gammes des variables présentées par les générateurs. Quand deux qualificateurs ou plus sont présent ils sont séparés par des virgules. Un exemple d'une compréhension de liste avec deux générateurs est donné par la définition suivante d'une fonction pour renvoyer une liste de toutes permutations d'une liste donnée,

   permanentes [] = [[]] permanentes X = [a : y | a < - x ; y < - permanentes (x [a])]

L'utilisation d'un filtre est montrée par la définition suivante d'une fonction ce qui prend un nombre et renvoie une liste de tous ses facteurs,

   facteurs n = [I | I < - [1. .n] ; `i = 0 de mod de `de n]

Les compréhensions de liste permettent souvent la concision remarquable de l'expression. Nous donnons deux exemples. Voici un rapport de Haskell de l'algorithme de « Quicksort » de Hoare, comme méthode d'assortir une liste,

   quicksort : : [a] - > quicksort [a] [] = [] quicksort (p : xs) = quicksort [quicksort de x | x < - xs, <= p de x] ++ [p] ++ [x | x < - xs, x > p]

Voici une solution de Haskell au problème de huit reines. Nous devons placer huit reines sur le conseil d'échecs de sorte qu'aucune reine ne donne le contrôle à tout autre. Puisque n'importe quelle solution doit avoir exactement une reine dans chaque colonne, une représentation appropriée pour un conseil est une liste de nombres entiers donnant le nombre de rangée de la reine dans chaque colonne successive. Dans le programme suivant la fonction les « reines n » renvoie toutes les manières sûres de placer des reines sur les premières colonnes de n. Une liste de toutes les solutions au problème de huit reines est donc obtenue en imprimant la valeur de (reines 8)

   reines 0 = [[]] reines (n+1) = [q : b | b < - reines n ; q < - [0..7] ; q sûr b] q sûr b = et [pas contrôles q b i | I < - [0. (b-1)] ] vérifie q b i = q=b ! ! ABS du || i (q - b ! ! i) =i+1

Évaluation paresseuse et listes infinies Le mécanisme de l'évaluation de Haskell est « paresseux », dans le sens qu'aucun subexpression n'est évalué jusqu'à ce que sa valeur soit exigée. Une conséquence de ceci est qui est possible pour définir les fonctions qui sont non-strictes (signification qu'elles sont capables de renvoyer une réponse même si un de leurs arguments est non défini). Par exemple nous pouvons définir une fonction conditionnelle comme suit,

   de x/y vrai de cond = de x/y faux de cond de x = y

et l'employer alors dans des situations telles que le « cond (x=0) 0 (1/x) ».

L'autre conséquence principale de l'évaluation paresseuse est qu'elle permet pour noter des définitions des structures de données infinies. Voici quelques exemples des définitions de Haskell des listes infinies (note qu'il y a une forme modifiée de « . » notation pour des progressions arithmétiques sans fin)

   nats = [0.] chance = [1.3.] ceux = 1 : ceux nums_from n = n : le nums_from (n+1) ajuste = [des xs d'odd_squares de ** 2 de x | x < - le nums_from 0] = [des ys de xs de ** de x 2 | x < - des xs, x impair] CP = [(x, y) | x < - les xs, y < - les ys]     -- Pyth cartésien de produit n = [(a, b, c) | a < - [1. .n],          -- Les triples pythagoriens b < - [1. .n], c < - [1. .n], a + les <= n de b + de c, a^2 + b^2 le == c^2] ajuste = [n*n | n < - [0.] ] mensonge = 1:1 : [a+b | (a, b) < - mensonge de fermeture éclair (mensonge de queue)] amorce = le passoir [2. ] où passoir (p : X) = p : passoir [répétition de n | n < - `p > 0 de mod de `de x, de n] a = x où x = a : X se perfectionne = [n | n < - [1.]; la somme (facteurs n) = n] amorce = le passoir [2. ] où passoir (p : X) = p : passoir [n | n < - x ; mod de n p > 0]

Les éléments d'une liste infinie sont « sur demande », de ce fait soulageant le programmeur d'indiquer l'écoulement calculé de commande de « consommateur-producteur ».

Une application intéressante des listes infinies est d'agir en tant que tables de consultation pour cacher les valeurs d'une fonction. Par exemple voici la définition (naïve) d'a d'une fonction pour calculer le nombre de Fibonacci de n'th :

   mentir 0 = 0 mensonges du mensonge 1 = 1 (n+2) = le mensonge (n+1) + le mensonge n

Cette définition naïve de « mensonge » peut être améliorée d'exponentiel à la complexité linéaire en changeant la récursion pour employer une table de consultation, ainsi

   mentir 0 = 1 mensonges du mensonge 1 = 1 (n+2) = flist ! ! (n+1) + flist ! ! n où mensonge de flist = de carte [0. ]

alternativement,

   mensonge n = fiblist ! ! n où fiblist = 1:1 : [a+b| (a, b) < - fermer la fermeture éclair le fiblist (fiblist de queue)]

Une autre utilisation importante des listes infinies est qu'ils nous permettent d'écrire des programmes fonctionnels représentant des réseaux des processus communiquants. Considérer par exemple le problème de nombres de Hamming - nous devons imprimer dans l'ordre croissant tous les nombres de la forme 2^a*3^b*5^c, pour a, b, c>=0. Il y a une solution gentille à ce problème en termes de processus communiquants, qui peuvent être exprimés en Haskell comme suit

   hamming = 1 : fusionner (F2) (fusion (f 3) (f 5))    

    là où f a = [fusion de n*a | n < - hamming] (a : X) (b : y) = a : fusion X (b : y), si a < b = b : fusion (a : X) y, si a > b = a : fusion de x/y, autrement 
 

Abstraction et généralisation

Haskell soutient l'abstraction de plusieurs manières :

   * là où expressions
   * définitions de fonction
   * abstraction de données
   * fonctions évoluées
   * évaluation paresseuse

Abstraction de données Haskell permet la définition des types abstraits, dont l'exécution est cachée du reste du programme. Pour nous montrer comment ceci fonctionne donnons l'exemple standard de définir la pile comme un type de données abstrait (ici basé sur des listes) :

   pile de module (StackType, poussée, bruit, dessus, vident) où des données StackType a = vide | la poussée X de Stk a (StackType a) s = bruit de Stk X s (Stk _ s) = dessus de s (Stk X _) = x vide = vident

Les constructeurs vident et Stk, qui comportent « l'exécution » ne sont pas exportés, et sont ainsi cachés en dehors de du module. Pour faire le béton de datatype, on écrirait :

   pile de module (StackType (vide, Stk), poussée,…) …

Fonctions évoluées Haskell est une langue entièrement évoluée --- les fonctions sont les premiers citoyens de classe et peuvent être passées comme paramètres et être retournées comme résultat. L'application de fonction est laissée associative, ainsi f de x/y elle est analysée en tant que (f X) y, signifiant que le résultat d'appliquer f à x est une fonction, qui est alors appliquée au Y.

En Haskell chaque fonction de deux arguments ou plus est réellement une fonction évoluée. Ceci permet la paramétrisation partielle. Par exemple le membre est une fonction de bibliothèque tels que membre X des essais si la liste X contient l'élément a (renvoi vrai ou faux comme approprié). En paramétrisant partiellement le membre nous pouvons dériver beaucoup d'attributs utiles, comme

   chiffre de voyelle = de membre [« a », « e », « I », « o », « u »] = mois du membre [« 0 », « 1 », « 2 », « 3 », « 4 », « 5 », « 6 », « 7 », « 8 », « 9 »] = membre [« janv. », « fév. », « mars », « avr. », « mai », « juin », « juillet », « août », « sept », « oct. », « nov. », « DEC »]

Comme un autre exemple de la programmation évoluée considèrent le foldr de fonction, défini près

   foldr k op [] = foldr k op (a de k : X) = a op (foldr k op X)

Toutes fonctions de traitement standard de liste peuvent être obtenues en paramétrisant partiellement le foldr. Voici quelques exemples.

   somme = foldr (+) 0 produits = foldr (*) 1 suffixe d'inverse = de foldr [] où suffixe x = x ++ [a]

Types de données abstraits Surcharge Dactylographier les classes Entrée-sortie Rangées Types Types simples Haskell fournit trois types simples, booléen, caractère et nombre.

Types Valeurs Bool Vrai, faux Char le jeu de caractères d'ASCII Interne minInt,…, maxInt Nombre entier nombres entiers arbitraires de précision Flotteur virgule flottante, précision simple Double virgule flottante, précision Casier nombres binaires Corde liste de caractères Funtions abstractions et définitions de lambda Listes listes d'objets du type T Tuples Types de données algébriques Nombres nombres entiers et nombres de virgule flottante Types composés Haskell fournit deux types, listes et tuples composés. La structure de données la plus utilisée généralement est la liste. Les éléments d'une liste doivent tout être du même type. En Haskell des listes sont écrites avec les crochets et les virgules. Les éléments d'un tuple peuvent être de du type mixte et des tuples sont écrits avec des parenthèses et des virgules. Les tuples sont analogues aux disques en Pascal (tandis que les listes sont analogues aux rangées). Les tuples ne peuvent pas être subscripted - leurs éléments sont accédés par l'assortiment de modèle.

Type Représentation Valeurs liste [liste séparée par virgule] défini pour l'utilisateur tuple (liste séparée par virgule) défini pour l'utilisateur

Voici plusieurs exemples des listes et d'un tuple :

   [] [« lundi », « Tue », « Wed », « Thur », « Fri »] [1.2.3.4.5] (« Jones », vrai, faux, 39)

Type déclarations Tandis que Haskell n'a pas besoin du type explicite déclarations (le type système d'inférence fournit la vérification statique), il est bon programmant la pratique de fournir le type explicite déclarations. Le type déclarations sont de la forme :

   e : : t

là où e est une expression et un t est un type. Par exemple, la fonction factorielle a le type

   fac : : Nombre entier - > nombre entier

tandis que la longueur de fonction qui renvoie la longueur d'une liste a le type

   longueur : : [a] - > nombre entier

là où [a] dénote une liste dont les éléments peuvent être n'importe quel type. Dactylographier les attributs Puisque Haskell fournit un type flexible système il fournit également le type attributs vérifient le type d'un objet. Haskell fournit trois le type attributs.

Attribut Vérifie si chiffre l'argument est un chiffre lettre l'argument est une lettre nombre entier l'argument est un nombre entier Expressions Opérateurs arithmétiques Haskell fournit les opérateurs arithmétiques standard.

Symbole Opération + addition - soustraction

• multiplication

/ vraie division division division de nombre entier mod module ^ à la puissance de Tuples (disques) Les éléments d'un tuple sont accédés par l'assortiment de modèle. Un exemple est donné dans une section postérieure. Opérateurs logiques La table suivante récapitule les opérateurs logiques.

Symbole Opération pas négation && conjonction logique || disjonction logique Attributs booléens La table suivante récapitule les opérateurs booléens.

Symbole Opération == égale /= pas égale < moins que <= moins qu'ou égale > plus grand que >= plus grand qu'ou égal Modules Au niveau supérieur, un programme de Haskell se compose d'une collection de modules. Un module est vraiment juste une grande déclaration qui commence par le module de mot-clé. Voici un exemple :

   arbre de module (arbre (feuille, branche), frange) où arbre de données a = feuille a | frange de branche (arbre a) (arbre a) : : Arbre a - > frange [a] (feuille X) = frange [x] (branche de gauche à droite) = droite laissée par frange de frange de ++

   y

Annexe Les fonctions suivantes font partie du prélude de norme de Haskell.

FONCTIONS BOOLÉENNES

&&

   et

||

   ou

pas

   et

autrement

   est equavalent pour rectifier.

FONCTIONS DE CARACTÈRE

ord chr isAscii, isControl, isPrint, isSpace, isUpper, isLower, isAlpha, isDigit, isAlphanum, toUpper, toLower

FONCTIONS NUMÉRIQUES

soustraire gcd, lcm x^n

   exposants positifs seulement

x^^n

   exposants positifs et négatifs

tronqué, rond, plafond, plancher

QUELQUES FONCTIONS DE NORME

fst (x, y)

   = x

snd (x, y)

   = y

(f.g) x

   = f (g X) -- composition en fonction

chiquenaude f de x/y

   = f y X

jusqu'à p f X

   donne le résultat d'appliquer f jusqu'à ce que p se tienne

==,/=, <, <=, >=, > de x/y maximum, minute de x/y +, -, * nier, ABS, signum, fromInteger toRational `de division de `, `de rem de `, `de mod de ` égal, impair divRem toInteger Opérateurs : +, -, *,/, ^ minInt, maxInt soustraire gcd lcm tronqué, rond, plafond, plancher pi exp, notation, sqrt

• • , logBase

péché, cos, bronzage asin, acos, atan sinh, matraque, tanh asinh, acosh, atanh

Le prélude PreludeList Haskell fournit un certain nombre d'opérations sur des listes. Haskell traite des cordes comme listes de caractères de sorte que les opérations et les fonctions de liste s'appliquent également aux cordes.

tête, queue

   extraire le premier élément et les éléments restants (respectivement) d'une liste non vide.

durer, init

   être conjugue de la tête et de la queue, en travaillant de la fin d'une liste finie plutôt que du commencement.

annuler, (++), (\ \) :

   déterminer la liste, la concaténation de liste (droit-associative), et la différence nulles de liste (non-associative) respectivement.

longueur

   renvoie la longueur d'une liste

! !

   est l'opérateur d'indice inférieur de liste d'infixe ; renvoie l'élément subscripted par l'index ; le premier élément de la liste a l'indice inférieur 0.

longueur

   renvoie la longueur de la liste.

carte

   s'applique son premier argument à chaque élément d'une liste (le deuxième argument) ; la carte (+2) [1.2.3] est [3.4.5]

filtre

   renvoie la liste d'éléments de son deuxième argument qui satisfont le premier argument ; le filtre (<5) [6.2.5.3] est [2.3]

cloison

   prend un attribut et une liste et renvoie une paire de listes, ces éléments de la liste d'argument qui satisfont et ne satisfont pas l'attribut

foldl, foldl1 scanl, scanl1 foldr, foldr1 scanr, scanr1 réitérer répéter x

   est les xs de liste = le x infinis : xs

xs de cycle

   est les xs infinis de liste = les xs des xs ++

xs de la prise n

   est la liste des premiers éléments de n des xs

xs de la baisse n

   est les xs de liste moins les premiers éléments de n

xs du splitAt n

   est la paire de listes obtenues à partir des xs par spliting le dans deux après l'élément de n^ {Th}

takeWhile dropWhile envergure coupure lignes, unlines mots, unwords pointe inverse et, ou quels, tous xs de l'elem X, xs de notElem de x

   sont les essais pour l'adhésion de liste

somme, produit sommes, produits maximum, minimum concat transposer passer comme un éclair, zip3--zip7 zipWidth, zipWidth3--zipWidth7

Prélude

   PreludeArray

Prélude

   PreludeText

Prélude

   PreludeIO

Références

Bird and Wadler

   Introduction to Functional Programming Prentice Hall, New York, 1988.

Field and Harrison

   Functional Programming Addison-Wesley, Workingham, England, 1988.

The Yale Haskell Group

   The Yale Haskell Users Manual Beta Release 1.1-0. May 1991.

Hudak, Paul et al.

   Report on the Programming Language Haskell Version 1.1 August 1991.

Peyton Jones, S. L.

   The Implementation of Functional Programming Languages Prentice-Hall, englewood Cliffs, NJ, 1987.

Permission is hereby granted, free of charge, to any person obtaining this work (the "Work"), to deal in the Work without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Work, and to permit persons to whom the Work is furnished to do so.

THE WORK IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE WORK OR THE USE OR OTHER DEALINGS IN THE WORK.

Last Modified - 05/21/2007 14:46:53. Comments and content invited aabyan@wwc.edu