Comment les algorithmes de programmation dynamique sont-ils implémentés dans Haskell idiomatique?

Question

Haskell et d'autres langages de programmation fonctionnels reposent sur le principe de ne pas maintenir l'état. Je ne connais pas encore le fonctionnement de la programmation fonctionnelle et les concepts qui y sont associés, alors je me demandais s'il était possible d'implémenter des algorithmes DP de manière FP.

Quelles constructions de programmation fonctionnelle peuvent être utilisées pour le faire?

Answer 1

La façon la plus courante de le faire est par l'intermédiaire de paresseux memoization. Dans un certain sens, la récursif de la fonction de fibonacci peut être considéré comme la programmation dynamique, car il calcule les résultats de chevauchement des sous-problèmes. Je réalise que c'est une fatigue exemple, mais voici un avant-goût. Il utilise les données memocombinators bibliothèque pour les paresseux memoization.

import qualified Data.MemoCombinators as Memo

fib = Memo.integral fib'
    where
    fib' 0 = 0
    fib' 1 = 1
    fib' n = fib (n-1) + fib (n-2)

fib est le memoized version, et fib' seulement "brute force" le problème, mais calcule ses sous-problèmes à l'aide de la memoized fib. D'autres DP algorithmes sont écrits dans le même style, à l'aide de différents mémo structures, mais la même idée du calcul du résultat dans une simple manière fonctionnelle et memoizing.

Edit: j'ai finalement cédé et a décidé de donner un memoizable typeclass. Cela signifie que memoizing est plus facile maintenant:

import Data.MemoCombinators.Class (memoize)

fib = memoize fib'
    where
    fib' :: Integer -> Integer  -- but type sig now required 
    ...

Instaead d'avoir besoin de suivre le type, vous pouvez juste memoize quoi que ce soit. Vous pouvez toujours utiliser l'ancienne méthode, si vous le souhaitez.

Answer 2

Rabhi et Lapalme de Algorithmes: Une Approche par Programmation Fonctionnelle a un beau chapitre sur ce qui illustre certaines FP concepts utilisés, à savoir des fonctions d'ordre supérieur et d'évaluation différée. Je suppose que c'est OK pour moi pour reproduire une version simplifiée de leur ordre supérieur de la fonction.

C'est simplifiée en ce qu'il ne fonctionne que sur des fonctions qui prennent des Int comme les intrants et les produits de type Int en sortie. Parce que nous utilisons Int de deux façons différentes, je vais faire des synonymes pour eux de la "Clé" et "Valeur". Mais n'oubliez pas que, parce que ce sont des synonynms, il est parfaitement possible d'utiliser des Clés et des Valeurs, et vice-versa. Ils sont utilisés uniquement pour des raisons de lisibilité.

type Key = Int
type Value = Int

dynamic :: (Table Value Key -> Key -> Value) -> Key -> Table Value Key
dynamic compute bnd = t
 where t = newTable (map (\coord -> (coord, compute t coord)) [0..bnd])

Nous allons disséquer cette fonction un peu.

Tout d'abord, ce que fait cette fonction? À partir de la signature de type, nous pouvons voir que c'est en quelque sorte manipule des tableaux. En effet, le premier argument de "calculer" est une fonction (donc dynamique est un "ordre supérieur" de la fonction) qui produit une sorte de valeur à partir d'une table, et le second argument est juste une sorte de limite supérieure, de nous dire où s'arrêter. Et en sortie, la "dynamique" de la fonction nous donne une sorte de Table. Si nous voulons obtenir la réponse à certaines DP-friendly problème, nous courons "dynamique" et ensuite chercher la réponse à partir de notre Tableau.

Pour utiliser cette fonction pour calculer fibonacci, nous courons un peu comme ceci

fib = findTable (dynamic helper n) n
 where
  helper t i =
    if i <= 1
       then i
       else findTable t (i-1) + findTable t (i-2)

Ne vous inquiétez pas trop à propos de la compréhension de cette fable de la fonction pour l'instant. Ça va devenir un peu plus clair que nous explorons "dynamique".

Deuxièmement, ce genre de conditions préalables ne nous avons besoin de connaître pour comprendre cette fonction? Je vais supposer que vous êtes plus ou moins familier avec la syntaxe, l' [0..x] pour indiquer une liste de 0 à x, l' -> type de signatures, comme Int -> Table -> ... contre l' -> dans les fonctions anonymes comme \coord -> ... Si vous n'êtes pas à l'aise avec eux, ils peuvent obtenir de la manière.

Une autre condition préalable pour résoudre cette Table de recherche. Nous ne voulons pas vous soucier de la façon dont il fonctionne, mais supposons que nous pouvons en créer une à partir de listes de paires clé-valeur et également rechercher des entrées dans les:

newTable :: [(k,v)] -> Table v k
findTable :: Table v k -> k -> v

Trois choses à noter ici:

• Pour des raisons de simplicité, nous ne sommes pas à l'aide de l'équivalent de la Haskell bibliothèque standard
• findTable plante si vous lui demandez de rechercher un inexistante valeur de la table. Nous pouvons utiliser un amateur de version pour éviter ce cas de besoin, mais c'est un sujet pour un autre post
• Curieusement, je n'ai pas parler de toute sorte de "ajouter une valeur à la table" de la fonction, même si le livre et la norme Haskell bibliothèques en fournir un. Pourquoi pas?

Enfin, comment cette fonction fonctionne réellement? Ce qui se passe ici? Nous pouvons zoomer un peu sur la viande de la fonction,

t = newTable (map (\coord -> (coord, compute t coord)) [0..bnd])

et méthodiquement la déchirent. En allant de l'extérieur, nous avons t = nouvelletable (...), qui semble nous dire que nous allons construire un tableau à partir d'un type de liste. Ennuyeux. Ce sur la liste?

map (\coord -> (coord, compute t coord)) [0..bnd]

Ici, nous avons l'ordre supérieur de la carte en fonction de la marche vers le bas d'une liste de 0 à bnd et de produire une nouvelle liste en conséquence. Pour calculer la nouvelle liste, c'est à l'aide d'une fonction \coord -> (coord, calculer t coord). Gardez à l'esprit le contexte: nous sommes en train de construire un tableau de valeur de la clé de paires, de sorte que si vous étudiez le tuple, la première partie coord doit être la clé et la seconde partie de calcul t coord doit être la valeur. Cette deuxième partie est là que les choses deviennent passionnantes. Zoomons un peu plus loin

compute t coord

Nous allons construire un tableau de paires clé-valeur et la valeur que nous comblons dans ces tables vient de la course "calculer t coord". Quelque chose que je n'ai pas mentionné plus tôt, c'est que calcul prend une table et une clé en entrée et qui nous dit quelle est la valeur que nous devons à brancher sur la table, en d'autres termes, quelle est la valeur que nous devrions nous associer à cette touche. L'idée ensuite, pour mettre de la programmation dynamique, est que le calcul de la fonction utilise les valeurs précédentes à partir de la table à calculer la nouvelle valeur que nous devons à brancher.

Et c'est tout! Pour faire de la programmation dynamique en Haskell nous pouvons construire une sorte de table successivement de brancher les valeurs dans les cellules en utilisant une fonction qui regarde en avant les valeurs de la table. Facile, droit?... ou est-il?

Peut-être vous avez une expérience similaire, comme je l'ai fait. Donc, je veux partager mes progrès aux prises avec cette fonction. Quand j'ai lu cette fonction, il semblait faire une sorte de logique intuitive, et je ne pense pas que beaucoup plus de celui-ci. Puis, j'ai lu ça de plus près et en fait une sorte de double-take, attendez quoi?! Comment cela peut-il travailler? Prendre un second regard sur cet extrait de code ici.

compute t coord

Pour calculer la valeur à une cellule donnée et donc compléter le tableau, nous passons en t, le tableau que nous essayons d'essayer de créer en premier lieu. Si la programmation fonctionnelle est sur l'immuabilité comme vous le soulignez, comment cette entreprise de valeurs, nous n'avons pas encore calculé éventuellement travailler? Si vous avez un peu de FP sous votre ceinture, vous pourriez vous demander, comme je l'ai fait, "est-ce une erreur?", ne devrait-ce pas être un "pli" au lieu de "carte"?

La clé ici est l'évaluation différée. Le peu de magie qui rend possible la création d'une valeur immuable à partir de morceaux de lui-même, tout revient à la paresse. Une sorte de long-terme-jaune-ceinture Haskeller, je trouve toujours la notion de paresse un peu décevant. Donc je vais laisser quelqu'un d'autre de prendre ici.

En attendant, j'ai tout simplement me dire que c'est OK. Je me contente de visualisation de la Table comme une sorte de point avec beaucoup de flèches qui sortait d'elle. La prise de fib à titre d'exemple:

o
|
|--0--> 1
|
|--1--> 1
|
|--2--> 2
|
|--3--> 2
.
.
.

Les bits de la table, nous n'avons pas encore vu, sont encore inconnues territoire. Quand nous avons commencé à marcher vers le bas de la liste de tous les inconnus

o
.
.
.

Lorsque l'on veut calculer la valeur première, nous n'avons pas besoin de savoir quelque chose de plus sur la table parce que i <= 1.

  helper t i =
    if i <= 1
       then i
       else findTable t (i-1) + findTable t (i-2)


o
|
|--0--> 1
.
.
.

Lorsque l'on veut calculer les valeurs successives, nous sommes toujours seuls, en regardant en arrière dans déjà découvert les pièces de la table (programmation dynamique, hé-hé!). L'essentiel à retenir, c'est que nous sommes 100% de travail avec des valeurs inaltérables ici, pas de fantaisie à côté de la paresse. "t" signifie vraiment la table, et non pas "le tableau dans son état actuel à l'itération 42". C'est juste que nous en découvrons les bits de la table qui nous disent ce que la valeur qui correspond à 42 est alors que nous demandons pour cela.

J'espère que d'autres sur StackOverflow, vous irez plus loin que moi et ne pas être laissé en marmonnant vaguement "euh ouais, la paresse ou de quelque chose d'autre" C'est vraiment pas une grosse affaire :-)

Answer 3

Si vous souhaitez utiliser le DP avec 2 ou 3 paramètres (par exemple, lors du traitement de chaînes de caractères), vous pouvez utiliser immuable tableau:

import Data.Array.IArray

answer :: String -> Int
answer s = table ! (1, l)
  where
    l = length s

    --signatyres are needed, because GHC doesn't know what kind of Array we need
    --string is stored in Array because we need quick access to individual chars
    a :: Array Int Char
    a = listArray (1, l) s

    table :: Array (Int, Int) Int
    table = listArray ((1, 1), (l, l)) [f i j | i <- [1..l], j <- [1..l]]

    f i j |    i    >     j    = 0
          |    i    ==    j    = 1
          | (a ! i) == (a ! j) = 2 + table ! (i+1, j-1)
          | otherwise          = maximum [table ! (i+1, j), table ! (i, j-1)]

Ce code résout les tâches suivantes: étant donné une chaîne de caractères S, trouver le sous-suite de S de longueur maximale, ce qui serait un palyndrome (sous-suite n'a pas besoin d'être continu).

Fondamentalement, 'f' est la resursive de la fonction, et le tableau "table" est une matrice de l'ensemble de ses valeurs possibles. Parce que Haskell est paresseux, uniquement nécessaire pour la réponse valeurs de f sont calculées. En d'autres termes, c'est la récursivité avec memoization. Afin d'utiliser les Données.Memocombinators, qui est la même, mais a déjà été écrit par quelqu'un d'autre :)

Answer 4

La programmation dynamique en haskell peut s’exprimer avec élégance grâce à la paresse, voir le premier exemple sur cette page

Answer 5

Les algorithmes de programmation dynamique habituellement exploiter l'idée de réduire un problème de plus simple problème(s). Ses problèmes peuvent être formulés comme base de faits (par exemple, le chemin le plus court à partir d'une cellule carrée pour lui-même est de longueur 0) ainsi qu'un ensemble de récurrence de règles qui montrent exactement comment réduire le problème de "trouver le chemin le plus court à partir de la cellule (i,j) de (0,0)" à problème "trouver des plus courts chemins à partir de cellules (i-1,j), (i,j-1) de (0,0); sélectionnez le meilleur". Autant que je sache, cela peut être facilement exprimées dans le style fonctionnel programme; pas de l'état concernés.