IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

A Gentle Introduction to Haskell, version 98


précédentsommairesuivant

XIII. Les Tableaux

Idéalement en programmation fonctionnelle, les tableaux devraient être vus comme des fonctions associant à un entier un élément du tableau. Mais si l'on souhaite être plus pragmatique, et donc privilégier les performances des accès aux éléments, on doit assurer quelques propriétés sur le domaine de ces fonctions, de façon à garder l'isomorphisme avec les sous-ensembles contigus d'entiers. Par conséquent, Haskell ne traitera pas les tableaux comme des fonctions, au sens le plus général du terme, mais plutôt comme un type de données abstrait avec une opération associée.

Il existe en gros deux grandes approches dans la gestion fonctionnelle des tableaux : la définition incrémentale, et la monolithique.
Dans l'approche incrémentale, on a une fonction renvoyant un tableau vide d'une taille donnée, et une autre qui prend un tableau, un index et une valeur, et qui renvoie un nouveau tableau qui diffère de celui passé en argument par la valeur au niveau de l'index donné en argument. Évidemment, une implantation naïve d'une telle méthode donnerait des performances désastreuses, car elle nécessite la recopie du tableau entier à chaque modification d'un élément (modification incrémentale) tout en donnant un temps de parcours linéaire. Par conséquent, toutes les tentatives sérieuses utilisent une approche employant une analyse statique fine, et des techniques rusées afin d'éviter les recopies excessives.
Dans l'approche monolithique, on construit le tableau complet en une fois, sans garder les valeurs intermédiaires du tableau. Bien que Haskell utilise un opérateur de mise à jour incrémentale pour les tableaux, la majeure partie de sa manipulation de tableaux est d'inspiration monolithique.

Les tableaux ne font pas partie du prélude standard, bien que la librairie standard intègre les opérateurs sur les tableaux. Il faut donc charger le module Array pour pouvoir les utiliser.

XIII-A. Les types d'indices

La librairie Ix définit une classe de type pour les indices de tableaux :

 
Sélectionnez
class  (Ord a) => Ix a  where
    range       :: (a,a) -> [a]
    index       :: (a,a) a -> Int
    inRange     :: (a,a) -> a -> Bool

Les déclarations d'instances sont effectuées pour les types Int, Integer, Char, Bool et les n-uplets de Ix dont la longueur est inférieure ou égale à 5. Par ailleurs, les instances peuvent être automatiquement dérivées pour les types n-uplets ou énumérés. On considère les types primitifs comme des indices de tableaux, et les n-uplets comme des indices de tableaux multidimensionnels. Remarquez que le premier argument de chaque opération de la classe Ix est une paire d'indices, qui sont les bornes (premier et dernier indices) du tableau. Par exemple, les bornes d'un tableau de 10 éléments d'un type Int, dont l'origine est nulle, seront (0,9), alors que celles d'un tableau de taille 100x100, dont l'origine est 1, seront ((1,1),(100,100)).
(Dans de nombreux autres langages, de telles bornes seraient écrites sous la forme 1:100, 1:100, mais la forme utilisée ici convient mieux au système de type, car chaque borne possède le même type que l'index)

L'opération range prend en argument une paire de bornes, et renvoie la liste des indices contenus entre ces bornes, dans l'ordre de l'index. Voici un exemple :

 
Sélectionnez
range (0,4) => [0,1,2,3,4]
 
range ((0,0),(1,2)) => [(0,0), (0,1), (0,2), (1,0), (1,1), (1,2)]

Le prédicat inRange détermine si un index est bien situé entre une paire de bornes donnée. (Pour un type nuplet, ce test est effectué composante par composante).
Morceau à corriger. Enfin, l'opération index autorise un élément particulier du tableau à être adressé directement. Étant donné une paire de bornes et un index in-range, l'opération va aligner l'ordinal de l'origine de l'index. Voici un exemple :

 
Sélectionnez
index (1,9) 2 => 1
 
index ((0,0),(1,2)) (1,1) => 4

XIII-B. Création d'un tableau

Dans Haskell, la fonction de création d'un tableau par la méthode monolithique renvoie un tableau à partir d'une paire de bornes et d'une liste de couple (index,valeur) (une liste associative)

 
Sélectionnez
array                   :: (Ix a) => (a,a) -> [(a,b)] -> Array a b

Ici, par exemple, on définit un tableau contenant les carrés des entiers de 1 à 100 :

 
Sélectionnez
squares                 =  array (1,100) [(i, i*i) | i <- [1..100]]

Cette expression d'un tableau est caractéristique dans l'utilisation de la compréhension qu'on a des listes pour construire des listes associatives. En fait, cette utilisation permet une compréhension des expressions de tableau similaires aux array comprehension du langage Id.

L'accès direct aux éléments d'un tableau est effectué par l'opérateur infixe !, et les bornes du tableau peuvent être obtenues avec la fonction bounds :

 
Sélectionnez
squares!7 => 49
 
bounds squares => (1,100)

On peut généraliser cet exemple en paramétrant les bornes et la fonction qui doit être appliquée à chaque index :

 
Sélectionnez
mkArray                 :: (Ix a) => (a -> b) -> (a,a) -> Array a b
mkArray f bnds          =  array bnds [(i, f i) | i <- range bnds]

Par conséquent, on peut définir squares comme mkArray (\i -> i * i) (1,100)

 
Sélectionnez
fibs    :: Int -> Array Int Int
fibs n  =  a  where a = array (0,n) ([(0, 1), (1, 1)] ++ 
                                     [(i, a!(i-2) + a!(i-1)) | i <- [2..n]])

Un autre exemple d'une telle récurrence est la matrice wavefront, dans laquelle les éléments de la première ligne et de la première colonne valent 1, et les autres valent la somme des éléments situés au nord, au nord-ouest et à l'ouest :

 
Sélectionnez
wavefront       :: Int -> Array (Int,Int) Int
wavefront n     =  a  where
                   a = array ((1,1),(n,n))
                        ([((1,j), 1) | j <- [1..n]] ++
                         [((i,1), 1) | i <- [2..n]] ++
                         [((i,j), a!(i,j-1) + a!(i-1,j-1) + a!(i-1,j))
                                     | i <- [2..n], j <- [2..n]])

On l'a appelée matrice wavefront, car dans une exécution en parallèle, la récurrence implique que l'exécution peut commencer avec la première ligne et la première colonne en parallèle, puis doit progresser comme une onde traversant la matrice du nord-ouest au sud-est. Il est important de signaler que, cependant, l'ordre de l'exécution n'est pas spécifié par la liste associative.

Dans chacun de nos exemples, on a donné une unique association pour chaque index du tableau, et seulement pour des indices situés entre les bornes du tableau. En effet, on doit faire cela de manière générale pour que le tableau soit complètement défini.
Une association avec un index dépassant les bornes produira une erreur. Si l'index manque ou apparaît plus d'une fois, il n'y aura cependant pas d'erreur immédiatement, mais la valeur du tableau à cet index sera non définie, et son accès produira une erreur.

XIII-C. Accumulation

On peut diminuer les contraintes lorsqu'un index apparaît au plus une fois dans la liste associative, en spécifiant comment combiner les valeurs multiples associées à un seul index. Le résultat est appelé un tableau accumulé.

 
Sélectionnez
accumArray :: (Ix a) -> (b -> c -> b) -> b -> (a,a) -> [Assoc a c] -> Array a b

Le premier argument de accumArray est la fonction d'accumulation, le second est la valeur initiale (la même pour chaque élément du tableau), et les arguments restants sont les bornes et la liste associative, comme avec la fonction array.
Un exemple typique serait d'avoir la fonction d'accumulation (+), et une valeur initiale 0. Ainsi, cette fonction prend en arguments une paire de bornes et une liste de valeurs (du type de l'index), et renvoie un histogramme, c'est-à-dire une table contenant le nombre d'occurrences de chaque valeur entre les bornes.

 
Sélectionnez
hist            :: (Ix a, Integral b) => (a,a) -> [a] -> Array a b
hist bnds is    =  accumArray (+) 0 bnds [(i, 1) | i <- is, inRange bnds i]

Supposons qu'on ait un ensemble de mesures situées dans un intervalle [a,b], et que l'on veuille diviser l'intervalle en dizaines, et compter le nombre de mesures présentes dans chaque sous-intervalle :

 
Sélectionnez
decades         :: (RealFrac a) => a -> a -> [a] -> Array Int Int
decades a b     =  hist (0,9) . map decade
                   where decade x = floor ((x - a) * s)
                         s        = 10 / (b - a)

XIII-D. Mises à jour incrémentales

En plus de ses fonctions de création de tableaux de manière monolithique, Haskell dispose aussi d'une fonction de mise à jour incrémentale pour les tableaux, écrite par l'opérateur infixe //. Le cas le plus simple est un tableau a ayant un élément i qu'il doit mettre à jour avec la valeur v. Cela s'écrit a // [(i, v)]. On doit utiliser un encadrement entre crochets, car l'argument gauche de (//) est une liste associative, qui contient généralement un ensemble d'indices du tableau qui lui est propre.

 
Sélectionnez
(//)            :: (Ix a) => Array a b -> [(a,b)] -> Array a b

Tout comme la fonction array, les indices d'une liste associative doivent être uniques pour que les valeurs associées puissent être définies. Par exemple, considérons une fonction qui intervertit deux lignes d'une matrice :

 
Sélectionnez
swapRows :: (Ix a, Ix b, Enum b) => a -> a -> Array (a,b) c -> Array (a,b) c
swapRows i i' a =  a // ([((i ,j), a!(i',j)) | j <- [jLo..jHi]] ++
                         [((i',j), a!(i ,j)) | j <- [jLo..jHi]])
                   where ((iLo,jLo),(iHi,jHi)) = bounds a

La concaténation de deux listes séparées dans une liste d'indices j n'est cependant pas vraiment efficace. Cela revient à écrire deux boucles imbriquées comme l'on ferait avec un langage impératif. Mais n'ayez crainte, on peut effectuer une optimisation proche de la fusion des boucles en Haskell :

 
Sélectionnez
swapRows i i' a =  a // [assoc | j <- [jLo..jHi],
                                 assoc <- [((i ,j), a!(i',j)),
                                           ((i',j), a!(i, j))] ]
                   where ((iLo,jLo),(iHi,jHi)) = bounds a

XIII-E. Un exemple : la multiplication matricielle

On peut compléter cette introduction aux tableaux en Haskell avec l'exemple typique de la multiplication matricielle, en se servant d'une surcharge d'une fonction bien plus générale. En effet, seules la multiplication et l'addition pour le type des éléments de la matrice sont nécessaires, on peut donc facilement écrire une fonction qui effectue la multiplication de matrices quelconques sans que cela exige beaucoup plus d'effort. Par ailleurs, si l'on fait attention à n'appliquer (!) et les opérations de Ix aux indices, on peut gagner en généricité sur les types des index, et en fait les types des index de lignes et de colonnes n'auront pas besoin d'être identiques. Par souci de simplicité, on demandera cependant que les indices à gauche des colonnes, et à droite des lignes soient de même type, et en plus que leurs bornes soient égales.

 
Sélectionnez
matMult         :: (Ix a, Ix b, Ix c, Num d) =>
                   Array (a,b) d -> Array (b,c) d -> Array (a,c) d
matMult x y     =  array resultBounds
                         [((i,j), sum [x!(i,k) * y!(k,j) | k <- range (lj,uj)])
                                       | i <- range (li,ui),
                                         j <- range (lj',uj') ]
        where ((li,lj),(ui,uj))         =  bounds x
              ((li',lj'),(ui',uj'))     =  bounds y
              resultBounds
                | (lj,uj)==(li',ui')    =  ((li,lj'),(ui,uj'))
                | otherwise             = error "matMult: incompatible bounds"

À côté de cela, on peut aussi définir matMult utilisant accumArray, et qui renverra le résultat sous une forme qui ressemble plus à la forme usuelle d'un langage impératif :

 
Sélectionnez
matMult x y     =  accumArray (+) 0 resultBounds
                              [((i,j), x!(i,k) * y!(k,j))
                                      | i <- range (li,ui),
                                        j <- range (lj',uj')
                                        k <- range (lj,uj)  ]
        where ((li,lj),(ui,uj))         =  bounds x
              ((li',lj'),(ui',uj'))     =  bounds y
              resultBounds
                | (lj,uj)==(li',ui')    =  ((li,lj'),(ui,uj'))
                | otherwise             = error "matMult: incompatible bounds"

On peut généraliser encore plus cette fonction en passant à l'ordre supérieur, juste en remplaçant sum et (*) par des fonctions passées en paramètres :

 
Sélectionnez
genMatMult      :: (Ix a, Ix b, Ix c) =>
                   ([f] -> g) -> (d -> e -> f) ->
                   Array (a,b) d -> Array (b,c) e -> Array (a,c) g
genMatMult sum' star x y  =
      array resultBounds
            [((i,j), sum' [x!(i,k) `star` y!(k,j) | k <- range (lj,uj)])
                                 | i <- range (li,ui),
                                   j <- range (lj',uj') ]
        where ((li,lj),(ui,uj))         =  bounds x
              ((li',lj'),(ui',uj'))     =  bounds y
              resultBounds
                | (lj,uj)==(li',ui')    =  ((li,lj'),(ui,uj'))
                | otherwise             = error "matMult: incompatible bounds"

Les fans d'APL reconnaîtront l'utilité des fonctions suivantes :

 
Sélectionnez
genMatMult maximum (-)
genMatMult and (==)

Avec la première, les arguments sont des matrices numériques, et l'élément (i,j) du résultat est le maximum de la différence entre les éléments correspondants à la ligne i du premier argument et la colonne j du second.
Avec la seconde, les arguments sont des matrices de type quelconque, et le résultat sera une matrice booléenne où chaque élément (i,j) est vrai si et seulement si la ligne i du premier argument et la colonne j du second sont égaux en tant que vecteurs.

Remarquez que les éléments de genMatMult n'ont pas besoin d'avoir des types identiques, mais seulement compatibles avec l'opérateur star passé en argument. On peut d'ailleurs encore généraliser en oubliant l'obligation que le type des lignes du premier argument soit identique à celui des colonnes du second. En effet, les deux matrices pourront être valides tant que la longueur des lignes du premier est égale à celle des colonnes du second.
Le lecteur peut souhaiter en dériver une version encore plus générale (indication: Utilisez l'opération index pour déterminer les longueurs)


précédentsommairesuivant

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2013 gorgonite. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.