J'apprends la programmation fonctionnelle (en Haskell) en réécrivant une partie de mon ancien code C ++. Un exemple sur lequel je travaille concerne la recherche de graphe Floyd-Warshall qui s'exécute sur une matrice de contiguïté NxN 2D pour trouver le chemin le plus court entre toutes les paires. Il utilise trois boucles for imbriquées pour analyser le tableau 2D et atteindre de manière itérative une solution.

Le code C ++ serait généralement:

int size = adjacencyMatrix.size();
for ( int k = 0; k < size; k++)
{
    for ( int i = 0; i < size; i++)
    {
        for ( int j = 0; j < size; j++)
        {
            double sum = adjacencyMatrix[i][k] + adjacencyMatrix[k][j];
            if ( sum < adjacencyMatrix[i][j] )
            {
                    adjacencyMatrix[i][j] = sum;
            }
        }
    }
}

La clé d'une telle recherche de graphe est sa méthode itérative. Par exemple, le code ci-dessus est très séquentiel; il ne peut être parallélisé que dans une mesure modérée car certains calculs ne peuvent être effectués tant que d'autres ne sont pas terminés.

De plus, avoir accès à l'index de la matrice signifie que certaines manipulations intelligentes au sein du tableau peuvent être effectuées. La boucle la plus interne de la recherche graphique ci-dessus utilise adjacencyMatrix[i][k], adjacencyMatrix[k][j] et adjacencyMatrix[i][j]. Je connais la fonction map dans Haskell, mais cela ne semble pas avoir la même puissance et la même flexibilité que l'utilisation d'indices de tableau.

En plus d'essayer de simuler une procédure impérative dans Haskell, je ne peux pas comprendre comment réécrire le code ci-dessus dans un style fonctionnel «pur».

Comment une procédure itérative qui utilise des boucles imbriquées complexes pour accéder aux index de tableau, comme la recherche de graphe ci-dessus, se traduit-elle en paradigme fonctionnel?

2
jla 3 avril 2017 à 08:03

2 réponses

Meilleure réponse

En plus d'essayer de simuler une procédure impérative dans Haskell, je ne peux pas comprendre comment réécrire le code ci-dessus dans un style fonctionnel «pur».

Je ne suis pas sûr que vous puissiez toujours réécrire un algorithme fondamentalement impératif dans un style fonctionnel. Cela dit, voici comment on traduirait votre exemple en Haskell. Notez qu'en général, chaque fois que vous avez vraiment besoin d'avoir des variables mutables pendant un moment, vous voudrez probablement utiliser le ST monade. Pour les tableaux, vous disposez de l 'array package.

Voici à quoi peut ressembler une traduction complète de cet algorithme

import Data.Array.Unboxed (UArray)
import Data.Array.ST (runSTUArray, newListArray, readArray, writeArray)
import Data.Maybe (fromMaybe)
import Control.Monad (when)
import Data.Foldable (for_)

-- | Takes as input the number of vertices, function to weigh edges, and returns
-- a matrix of the shortest distance between every two vertices.
floydWarshall :: Int -> ((Int,Int) -> Maybe Double) -> UArray (Int,Int) Double
floydWarshall n weight = runSTUArray $ do
    -- initialize the array with the right values
    arr <- newListArray ((0,0),(n-1,n-1))
                        [ if i == j then 0 else fromMaybe (1 / 0) (weight (i,j))
                        | i<-[0..(n-1)], j<-[0..(n-1)] ]

    -- iteratively improve the shortest distances
    for_ [0..(n-1)] $ \k ->
      for_ [0..(n-1)] $ \i ->
        for_ [0..(n-1)] $ \j -> do
          arr_ik <- readArray arr (i,k)
          arr_kj <- readArray arr (k,j)
          arr_ij <- readArray arr (i,j)
          let sum = arr_ik + arr_kj
          when (sum < arr_ij)
            (writeArray arr (i,j) sum)

    return arr
6
Alec 3 avril 2017 à 09:33

La meilleure option est d'utiliser le package Data.Vector et d'utiliser ifoldl avec des imaps imbriquées qui ressembleront à ceci:

{-# LANGUAGE OverloadedLists #-}

import Data.Vector

type Matrix a = Vector (Vector a)

floydwarshall mat = ifoldl (\m k _ ->
                               imap (\i row ->
                                       imap (\j v -> 
                                               (m!i!k + m!k!j) `min` v) row) m) mat mat

Ifoldl et imap aux côtés des valeurs stockées dans des cartes vectorielles en utilisant leurs indices, ce qui vous permet d'appeler des valeurs à un index spécifique. Le foldl est nécessaire pour accumuler tous les changements dans les itérations de k tout en gardant la structure immuable. À l'intérieur des imaps, vous devez indexer à l'intérieur de la matrice m qui est notre accumulateur pour foldr et qui conserve toutes les modifications.

Si vous ne souhaitez pas importer de packages, vous pouvez toujours implémenter imap et ifoldl pour les listes de prélude stock

imap :: (Int -> a -> b) -> [a] -> [b]
imap f = map (uncurry f) . zip [0,1..]

ifoldl :: (b -> Int -> a -> b) -> b -> [a] -> b
ifoldl f acc = foldl (\ac -> uncurry (f ac)) acc . zip [0,1..]

MODIFIÉ: selon la suggestion de @chi

4
Antisthenes 3 avril 2017 à 09:31