Quelqu'un peut-il expliquer le concept derrière la mémorisation de Haskell?

(notez que je pose la question ici parce qu'il s'agit de la mécanique conceptuelle de celui-ci, plutôt que d'un problème de codage)

Je travaillais sur un petit programme, qui utilisait une séquence de nombres de fibonacci dans son équasion, mais j'ai remarqué que si je dépassais un certain nombre, cela devenait douloureusement lent, en parcourant un peu les choses Memoization, je suis tombé sur une technique à Haskell connue sous le nom de , ils ont montré que le code fonctionnait comme ceci:

-- Traditional implementation of fibonacci, hangs after about 30
slow_fib :: Int -> Integer
slow_fib 0 = 0
slow_fib 1 = 1
slow_fib n = slow_fib (n-2) + slow_fib (n-1)

-- Memorized variant is near instant even after 10000
memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib (n-2) + memoized_fib (n-1)

Donc, ma question est la suivante: comment ou plutôt pourquoi cela fonctionne-t-il?

Est-ce parce qu'il parvient en quelque sorte à parcourir la majeure partie de la liste avant que le calcul ne rattrape? Mais si haskell est paresseux, il n'y a pas vraiment de calcul à rattraper ... Alors comment ça marche?

Juste pour expliquer la mécanique derrière la mémorisation réelle,

memo_fib = (map fib [1..] !!)

produit une liste de "thunks", calculs non évalués. Pensez à ces cadeaux comme non ouverts, tant que nous ne les toucherons pas, ils ne fonctionneront pas.

Maintenant, une fois que nous évaluons un thunk, nous ne l'évaluons plus jamais. Il s'agit en fait de la seule forme de mutation dans le haskell "normal", les thunks mutent une fois évalués pour devenir des valeurs concrètes.

Donc, revenons à votre code, vous avez une liste de thunks, et vous faites toujours cette récursivité d'arbre, mais vous récursivement en utilisant la liste, et une fois qu'un élément de la liste est évalué, il n'est plus jamais calculé à nouveau. Ainsi, nous évitons la récursivité des arbres dans la fonction fib naïve.

Comme note tangentiellement intéressante, cela est particulièrement rapide sur une série de nombres de fibonnaci sont calculés car cette liste n'est évaluée qu'une seule fois, ce qui signifie que si vous calculez memo_fib 10000deux fois, la deuxième fois doit être instantanée. En effet, Haskell n'a évalué les arguments des fonctions qu'une seule fois et vous utilisez une application partielle au lieu d'un lambda.

TLDR: En stockant les calculs dans une liste, chaque élément de la liste est évalué une fois, par conséquent, chaque nombre de fibonnacci est calculé exactement une fois tout au long du programme.

Visualisation:

 [THUNK_1, THUNK_2, THUNK_3, THUNK_4, THUNK_5]
 -- Evaluating THUNK_5
 [THUNK_1, THUNK_2, THUNK_3, THUNK_4, THUNK_3 + THUNK_4]
 [THUNK_1, THUNK_2, THUNK_1 + THUNK_2, THUNK_4, THUNK_3 + THUNK_4]
 [1, 1, 1 + 1, THUNK_4, THUNK_3 + THUNK_4]
 [1, 1, 2, THUNK_4, 2 + THUNK4]
 [1, 1, 2, 1 + 2, 2 + THUNK_4]
 [1, 1, 2, 3, 2 + 3]
 [1, 1, 2, 3, 5]

Vous pouvez donc voir comment l'évaluation THUNK_4est beaucoup plus rapide car ses sous-expressions sont déjà évaluées.

Le point de mémorisation n'est jamais de calculer deux fois la même fonction - cela est extrêmement utile pour accélérer des calculs purement fonctionnels, c'est-à-dire sans effets secondaires, car pour ceux-ci, le processus peut être entièrement automatisé sans affecter l'exactitude. Ceci est particulièrement nécessaire pour des fonctions comme fibo, qui conduisent à une récursivité d'arbre , c'est-à-dire un effort exponentiel, lorsqu'elles sont implémentées naïvement. (C'est une des raisons pour lesquelles les nombres de Fibonacci sont en fait un très mauvais exemple pour enseigner la récursivité - presque toutes les implémentations de démonstration que vous trouvez dans les tutoriels ou les livres sont inutilisables pour les grandes valeurs d'entrée.)

Si vous tracez le flux d'exécution, vous verrez que dans le second cas, la valeur de fib xsera toujours disponible quand il fib x+1sera exécuté, et le système d'exécution pourra simplement le lire depuis la mémoire plutôt que via un autre appel récursif, tandis que le la première solution essaie de calculer la plus grande solution avant que les résultats pour les valeurs plus petites ne soient disponibles. C'est finalement parce que l'itérateur [0..n]est évalué de gauche à droite et va donc commencer par 0, tandis que la récursivité dans le premier exemple commence par net seulement alors demande à propos de n-1. C'est ce qui conduit aux nombreux, nombreux appels de fonctions en double inutiles.