Les tableaux

Idéalement, les tableaux dans un langage fonctionnel devraient être considérés simplement comme des fonctions allant d'indices à des valeurs, mais pragmatiquement, afin d'assurer un accès efficace aux éléments du tableau, nous devons être sûrs de pouvoir tirer parti des propriétés spéciales des domaines de ces fonctions, étant isomorphes à des sous-ensembles contigus finis d'entiers. Haskell, par conséquent, ne traite pas les tableaux comme des fonctions générales avec une opération d'application, mais comme des types de données abstraits avec une opération d'indice.

Deux approches principales des tableaux fonctionnels peuvent être distinguées : la définition incrémentale et la définition monolithique. Dans le cas incrémental, nous avons une fonction produisant un tableau vide d'une taille donnée et une autre prenant un tableau, un index et une valeur, produisant un nouveau tableau ne différant de l'ancien qu'à l'index donné. De toute évidence, une implémentation naïve d'une telle sémantique de tableau serait intolérablement inefficace, nécessitant soit une nouvelle copie d'un tableau pour chaque redéfinition incrémentale, soit un temps linéaire pour la recherche de tableau ; Ainsi, les tentatives sérieuses d'utilisation de cette approche utilisent une analyse statique sophistiquée et des dispositifs d'exécution intelligents pour éviter une copie excessive. L'approche monolithique, en revanche, construit un tableau en une seule fois, sans référence aux valeurs intermédiaires du tableau. Bien que Haskell dispose d'un opérateur de mise à jour de tableau incrémental, l'essentiel de la fonctionnalité de tableau est monolithique.

Les tableaux ne font pas partie du prélude standard --- la bibliothèque standard contient les opérateurs de tableau. Tout module utilisant des tableaux doit importer le module Array.

Types d'index

La bibliothèque Ix définit une classe de types d'index de tableau :

Des déclarations d'instances sont fournies pour les types Int, Integer, Char, Bool et les tuples de type Ix jusqu'à une longueur de 5 ; en outre, des instances peuvent être automatiquement dérivées pour les types énumérés et tuples. Nous considérons les types primitifs comme des index vectoriels et les tuples comme des indices de tableaux rectangulaires multidimensionnels. Notez que le premier paramètre de chacune des opérations de la classe Ix est une paire d'indices ; il s'agit généralement des limites (premier et dernier indices) d'un tableau. Par exemple, les limites d'un vecteur de 10 éléments à origine zéro avec des indices Int seraient (0,9), tandis qu'une matrice de 100 par 100 à origine unique pourrait avoir les limites ((1,1),(100,100)). (Dans de nombreux autres langages, ces limites seraient écrites sous une forme telle que 1:100, 1:100, mais la forme actuelle correspond mieux au système de types, puisque chaque limite est du même type qu'un index général.)

L'opération d'intervalle prend une paire de limites et produit la liste des indices compris entre ces limites, dans l'ordre des index. Par exemple :

Le prédicat inRange détermine si un index se situe entre une paire de limites donnée. (Pour un type de tuple, ce test est effectué composante par composante.) Enfin, l'opération d'index permet d'adresser un élément particulier d'un tableau : étant donné une paire de limites et un index dans l'intervalle, l'opération donne l'ordinal d'origine zéro de l'index dans l'intervalle; par exemple :

Création de tableau

La fonction de création de tableau monolithique de Haskell forme un tableau à partir d'une paire de limites et d'une liste de paires index-valeur (une liste d'associations) :

Voici, par exemple, une définition d'un tableau de carrés de nombres de 1 à 100 :

Cette expression de tableau est typique de l'utilisation d'une compréhension de liste pour la liste d'associations; en fait, cette utilisation donne lieu à des expressions de tableau très similaires aux compréhensions de tableau de l'ID de langue [6].

L'indexation de tableau est effectuée avec l'opérateur infixe !, et les limites d'un tableau peuvent être extraites avec la fonction bounds :

Nous pourrions généraliser cet exemple en paramétrant les limites et la fonction à appliquer à chaque index :

Ainsi, nous pourrions définir des carrés comme mkArray (\i -> i * i) (1,100).

De nombreux tableaux sont définis de manière récursive, c'est-à-dire que les valeurs de certains éléments dépendent des valeurs d'autres. Ici, par exemple, nous avons une fonction renvoyant un tableau de nombres de Fibonacci :

Un autre exemple d'une telle récurrence est la matrice de front d'onde n par n, dans laquelle les éléments de la première ligne et de la première colonne ont tous la valeur 1 et les autres éléments sont des sommes de leurs voisins à l'ouest, au nord-ouest et au nord :

La matrice de front d'onde est ainsi appelée car dans une implémentation parallèle, la récurrence dicte que le calcul peut commencer par la première ligne et la première colonne en parallèle et se dérouler comme une onde en forme de coin, se déplaçant du nord-ouest au sud-est. Il est important de noter, cependant, qu'aucun ordre de calcul n'est spécifié par la liste d'association.

Dans chacun de nos exemples jusqu'à présent, nous avons donné une association unique pour chaque index du tableau et uniquement pour les index dans les limites du tableau, et en fait, nous devons le faire en général pour qu'un tableau soit entièrement défini. Une association avec un index hors limites entraîne une erreur; si un index est manquant ou apparaît plus d'une fois, cependant, il n'y a pas d'erreur immédiate, mais la valeur du tableau à cet index est alors indéfinie, de sorte que l'inscription du tableau avec un tel index génère une erreur.

Accumulation

Nous pouvons assouplir la restriction selon laquelle un index n'apparaît qu'une seule fois dans la liste d'association en spécifiant comment combiner plusieurs valeurs associées à un seul index ; le résultat est appelé un tableau accumulé :

Le premier paramètre de accumArray est la fonction d'accumulation, le second est une valeur initiale (la même pour chaque élément du tableau) et les paramètres restants sont des limites et une liste d'associations, comme avec la fonction de tableau. En général, la fonction d'accumulation est (+) et la valeur initiale, zéro; par exemple, cette fonction prend une paire de limites et une liste de valeurs (de type index) et génère un histogramme, c'est-à-dire un tableau du nombre d'occurrences de chaque valeur dans les limites :

Supposons que nous ayons une collection de mesures sur l'intervalle [a, b], et que nous voulions diviser l'intervalle en décennies et compter le nombre de mesures dans chacune :

Mises à jour incrémentielles

En plus des fonctions de création de tableaux monolithiques, Haskell dispose également d'une fonction de mise à jour incrémentielle de tableaux, écrite sous la forme de l'opérateur infixe // ; le cas le plus simple, un tableau a avec l'élément i mis à jour à v, s'écrit a // [(i, v)]. La raison des crochets est que le paramètre de gauche de (//) est une liste d'associations, contenant généralement un sous-ensemble approprié des indices du tableau :

Comme pour la fonction array, les indices de la liste d'associations doivent être uniques pour que les valeurs soient définies. Par exemple, voici une fonction permettant d'interchanger deux lignes d'une matrice :

La concaténation ici de deux compréhensions de listes distinctes sur la même liste d'indices j est cependant légèrement inefficace ; c'est comme écrire deux boucles là où une seule suffirait dans un langage impératif. N'ayez crainte, nous pouvons effectuer l'équivalent d'une optimisation par fusion de boucles en Haskell :

Un exemple : multiplication de matrices

Nous terminons notre introduction aux tableaux Haskell avec l'exemple familier de la multiplication de matrices, en tirant parti de la surcharge pour définir une fonction assez générale. Comme seules la multiplication et l'addition sur le type d'élément des matrices sont impliquées, nous obtenons une fonction multipliant les matrices de tout type numérique, à moins que nous ne fassions de gros efforts pour ne pas le faire. De plus, si nous prenons soin d'appliquer uniquement (!) et les opérations de Ix aux index, nous obtenons la généricité sur les types d'indices, et en fait, les quatre types d'indices de ligne et de colonne n'ont pas besoin d'être tous identiques. Pour plus de simplicité, cependant, nous exigeons que les indices de colonne de gauche et les indices de ligne de droite soient du même type, et de plus, que les bornes soient égales :

En passant, nous pouvons également définir matMult en utilisant accumArray, ce qui donne une présentation qui ressemble davantage à la formulation habituelle dans un langage impératif :

Nous pouvons généraliser davantage en rendant la fonction d'ordre supérieur, en remplaçant simplement sum et (*) par des paramètres fonctionnels :

Les fans de l'APL reconnaîtront l'utilité de fonctions telles que les suivantes :

Dans le premier cas, les paramètres sont des matrices numériques et le (i,j)-ième élément du résultat est la différence maximale entre les éléments correspondants de la i-ième ligne et de la j-ième colonne des entrées. Dans le second cas, les paramètres sont des matrices de n'importe quel type d'égalité et le résultat est une matrice booléenne dans laquelle l'élément (i,j) est vrai si et seulement si la i-ième ligne du premier paramètre et la j-ième colonne du second sont égales en tant que vecteurs.

Notez que les types d'éléments de genMatMult n'ont pas besoin d'être identiques, mais simplement appropriés pour le paramètre de fonction star. Nous pourrions généraliser encore davantage en abandonnant l'exigence selon laquelle les types d'index de la première colonne et de la deuxième ligne doivent être identiques; il est clair que deux matrices peuvent être considérées comme conformes tant que les longueurs des colonnes de la première et des lignes de la seconde sont égales. Le lecteur peut souhaiter dériver cette version encore plus générale. (Astuce : utilisez l'opération d'index pour déterminer les longueurs.)