A Gentle Introduction to Haskell, version 98

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

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 :

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 :

index (1,9) 2 => 1
 
index ((0,0),(1,2)) (1,1) => 4

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)

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 :

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 :

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 :

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)

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 :

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.

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é.

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.

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 :

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)

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.

(//)            :: (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 :

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 :

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

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.

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 :

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 :

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 :

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)