managment appel mémoire queue haskell

Question

J'utilise la structure de commande suivante (qui je pense est récursive de la queue)

untilSuccessOrBigError :: (Eq e) => (Integer -> (Either e a)) -> Integer -> e -> (Either e a) 
untilSuccessOrBigError f count bigError 
    = case f count of 
     Right x -> Right x 
     Left e -> (if e==bigError then Left e else untilSuccessOrBigError f (count - 1) e) 

faire itérative l'approfondissement

iterativeDeepening :: (a -> [a]) -> (a -> Bool) -> (a -> Bool) -> a -> Either String a 
iterativeDeepening stepFunc isAValidSolution isGraphBottom x 
    = untilSuccessOrBigError 
     (\count -> dfsWithMaxDepth stepFunc isAValidSolution isGraphBottom count x) 
     (-1) 
     "Reached graph bottom" 

sera cette mémoire libre (puisqu'il ne sera plus techniquement capable de l'atteindre) qu'après chaque approfondissement itératif, sinon comment dois-je réécrire la structure de contrôle?

P.S. À la seconde, il semblerait que cela échouera car les structures récursives de la queue sont souvent capables d'accéder à des choses sur la pile comme si elles s'ajoutaient à la valeur précédente, même si ce n'est pas le cas dans ce cas. - Roman A. Taycher 28 novembre à 12h33 P.P.S. Sur le troisième, cela me fait penser qu'il peut rejeter les valeurs à l'intérieur de dfsWithMaxDepth dès que dfsWithMaxDepth revient et qu'un tas de réponses ne prend pas beaucoup de mémoire. - Roman A. Taycher nov 2

Answer 1

À première vue, il n'y a aucune raison que cela ne sera pas correctement les déchets collectés, et pourquoi TCO ne sera pas exécutée.

En général, vous devriez penser à tco et la collecte des ordures d'une manière différente dans Haskell - beaucoup de questions connexes énumérés ici semblent très serviable. Fondamentalement, vous voulez imaginer la sémantique opérationnelle de GHC Haskell comme une réduction paresseuse de graphique.

Imaginez que vous avez juste l'ensemble AST en mémoire, avec des flèches supplémentaires de chaque utilisation d'un nom à sa définition, et vous demandez la valeur de « principale. » Maintenant, pour obtenir cela, vous devez regarder la valeur de la première fonction appelée dans main, et le remplacer, ce qui signifie que vous devez chasser la prochaine chose qui doit être évaluée, etc Maintenant, à un moment donné dans cette réduction, vous remarquerez que les choses qui étaient utilisées comme expressions ont maintenant été calculées et remplacées par les valeurs qu'elles représentent. Ensuite, ces expressions peuvent être récupérées. Pendant ce temps, la trace que vous avez du haut du graphique jusqu'au morceau que vous êtes en train d'évaluer est la "pile". Donc, si pour évaluer une structure, vous devez évaluer "à l'intérieur" de cette structure, alors cela va augmenter votre pile.

Ce qui précède est bâclée et handwavy, mais pourrait aider à donner une intuition.