Memoization pascals triangle

Question

Je ne suis pas intéressé par la solution réelle ou d'autres méthodes de résolution du problème, il est le memoization i besoin d'aide :)

je besoin d'aide pour faire un problème de triangle pascals avec memoization. Je veux obtenir le numéro du milieu dans la base du triangle. (Euler projet 15)

Le premier exemple est pas memoized (bien que son nom l'indique si) « 20 20 » non résolvable

deuxième tentative est une tentative de faire quelque chose de similaire à: http://www.haskell.org/haskellwiki/Memoization

troisième est Hlints suggestion sur no2 si c'est plus lisible pour quelqu'un.

je reçois cette erreur, mais je ne suis pas sûr de son droit, même si elle rassemblerait ... (courir à partir ghci avec 2 2 comme params

no instance for (Num [a0]) 
arising from a use of `zmemopascals' 
Possible fix: add an instance declaration for (Num [a0]) 
In the expression: zmemopascals 2 2 
In an equation for `it': it = zmemopascals 2 2 

.

Code: 
--1 
memopascals r c = [[pascals a b | b<-[1..c]] | a<-[1..r]] !! (r-1) !! (c-1) 
where pascals 1 _ = 1 
     pascals _ 1 = 1 
     pascals x y = memopascals (x-1) y + memopascals x (y-1) 

--2 
--xmemopascals :: Int -> Int -> Int 
xmemopascals r c = map (uncurry pascals) (zip [1..] [1..]) !! (r-1) !! (c-1) 
where pascals 1 _ = 1 
     pascals _ 1 = 1 
     pascals x y = memopascals (x-1) y + memopascals x (y-1) 


--3 
zmemopascals r c = zipWith pascals [1 ..] [1 ..] !! (r-1) !! (c-1) 
where pascals 1 _ = 1 
     pascals _ 1 = 1 
     pascals x y = memopascals (x-1) y + memopascals x (y-1) 

Answer 1

Il existe plusieurs solutions pour atteindre memoization (jetez un oeil here pour une discussion récente).

D'abord, utilisez l'option -O2 avec le compilateur GHC. Deuxièmement, utilisez une signature de type monomorphe. Nommez votre (vos) liste (s) intermédiaire (s), que vous souhaitez partager.

Ensuite, faites attention à vos définitions imbriquées. Si une définition imbriquée dépend de la valeur d'un argument dans sa portée englobante ("externe"), cela signifie que chaque appel à cette fonction externe devra créer à nouveau toutes ses définitions imbriquées, donc il n'y aura pas de liste une être partagé, mais beaucoup séparés indépendants.

Ici, dans votre fonction, séparant et en nommant l'expression de la liste que vous voulez partagiez, nous obtenons

memopascals r c = xs !! (r-1) !! (c-1) 
where 
    xs = [[pascals a b | b<-[1..c]] | a<-[1..r]] 
    pascals 1 _ = 1 
    pascals _ 1 = 1 
    pascals x y = memopascals (x-1) y + memopascals x (y-1) 

Votre définition xs dépend sur les valeurs de r et c, mais vous appelez votre « externe "fonction, memopascals, à partir d'un imbriqué, pascals. Chaque invocation de memopascalsa pour créer sa propre copie de xs car elle dépend des arguments de memopascals, r et c. Pas de partage possible.

Si vous avez besoin de cette définition dépendante, vous devez faire en sorte de ne pas appeler "hors portée", mais plutôt rester dans cette portée, afin que toutes les définitions internes ("imbriquées") puissent être réutilisées.

memopascals r c = f r c 
where 
    f r c = xs !! (r-1) !! (c-1) 
    xs = [[pascals a b | b<-[1..c]] | a<-[1..r]] 
    pascals 1 _ = 1 
    pascals _ 1 = 1 
    pascals x y = f (x-1) y + f x (y-1) 

Maintenant, chaque invocation de memopascals crée ses définitions internes (de son champ d'application imbriquée) qui appellent alors les uns des autres, appelant jamais hors de portée - si la liste xs obtient réutilisés, parvenir à un partage.

Mais un autre appel à memopascals va créer sa propre nouvelle copie de sa définition interne de la liste xs et utilisera il. Nous pouvons appeler cela un partage "local", pas un partage "global" (c'est-à-dire mémo). Cela signifie qu'il fonctionne rapidement, mais le second appel avec les mêmes paramètres prend le même temps que le premier - pas le 0 comme avec une mémo complète.

Il n'y a qu'une seule façon d'atteindre que, et de rendre votre définition de xs indépendante. Ensuite, le compilateur peut briser toutes les possibilités imbriquée cadres ensemble, effectuer lambda lifting tournant imbriquées les fermetures en plaine lambdas, etc., etc .:

memopascals :: Int -> Int -> Integer 
memopascals r c = [[pascals a b | b<-[1..]] | a<-[1..]] !! (r-1) !! (c-1) 
where 
    pascals 1 _ = 1 
    pascals _ 1 = 1 
    pascals x y = memopascals (x-1) y + memopascals x (y-1) 

Avec le commutateur -O2, GHC effectue memoization complète même pour cette version .Tant que nous n'oublions pas la signature de type monomorphe (ou encore le partage local).

Answer 2

Memoization ne fonctionne pas dans vos fonctions parce qu'un appel comme memopascals 5 5 construit intérieurement une partie du triangle et renvoie une seule valeur de celui-ci.Un autre appel mempascals 6 6 n'a pas de connexion à ce triangle partiel interne à memopascals 5 5

Pour une mémoisation efficace, vous souhaitez que la partie commune (comme la liste des listes représentant les nombres calculés dans le triangle) soit une fonction distincte, qui est ensuite utilisée par les fonctions qui accèdent à des index spécifiques. De cette façon, vous utilisez la même liste de listes pour rechercher différents index.

Habituellement, la meilleure façon de le faire est d'écrire une fonction comme fullpascals :: [[Int]] qui produit la structure de données complète (infinie), et qu'une autre fonction pour accéder à cette structure de données, comme

memopascals x y = fullpascals !! (x-1) !! (y-1) 

Dans votre cas fullpascals serait le même que l'une de vos fonctions actuelles, mais sans les paramètres pour un index spécifique. Il peut même encore utiliser memopascals en interne pour la récursivité.

---

Sidenote: Dans l'exemple memoized_fib dans le wiki, la partie « commune » qui est memoized est pas directement la liste de tous les bobards, mais une fonction qui accède à la liste de tous les bobards. L'effet est le même, puisque le compilateur est assez intelligent pour optimiser cela.

Answer 3

zmemopascals r c = zipWith pascals [1 ..] [1 ..] !! (r-1) !! (c-1) 
where pascals 1 _ = 1 
     pascals _ 1 = 1 
     pascals x y = memopascals (x-1) y + memopascals x (y-1) 

Non qu'il compte pour l'erreur, mais dans la dernière ligne, vous voulez appeler zmemopascals plutôt que memopascals.

Dans la première ligne, vous avez deux opérateurs d'index de liste. Donc zipWith pascals [1 .. ] [1 .. ] doit avoir le type [[a]] pour certains a. La définition de pascals dit

pascals :: Num t => Int -> Int -> t 

ainsi zipWith pascals [1 .. ] [1 .. ] :: [t]. Par conséquent l'inférence de type trouve que t = [a], mais le compilateur ne trouve pas une instance Num [a].Pour la memoisation, vous devez donner un nom au triangle complet, comme @sth suggéré, pour éviter le recalcul (la memoisation de Fibonacci ne fonctionne que parce que le compilateur est assez intelligent, ce n'est pas garanti par sa forme).

Une autre option serait de construire le triangle à l'aide iterate,

pascal :: Int -> Int -> Integer 
pascal n k = iterate nextRow [1] !! n !! k 
    where 
    nextRow ks = zipWith (+) (0:ks) (ks ++ repeat 0)