Je n’utilise pas beaucoup ST, mais c’est parfois la meilleure solution. Cela peut être dans de nombreux scénarios:

• Il existe déjà des moyens efficaces et bien connus pour résoudre un problème. Quicksort en est un exemple parfait. Il est connu pour sa rapidité et son comportement sur place, qui ne peut pas être très bien imité par du code pur.
• Vous avez besoin de limites de temps et d’espace rigides. Surtout avec l’évaluation paresseuse (et Haskell ne précise même pas s’il y a une évaluation paresseuse, mais si elle est non ssortingcte), le comportement de vos programmes peut être très imprévisible. La présence d’une fuite de mémoire peut dépendre de l’activation d’une certaine optimisation. Ceci est très différent du code impératif, qui a un ensemble fixe de variables (généralement) et un ordre d’évaluation défini.
• Vous avez une date limite. Bien que le style pur soit presque toujours une meilleure pratique et un code plus propre, si vous avez l’habitude d’écrire impérativement et que vous avez besoin du code rapidement, commencer impérativement et passer à la fonctionnalité ultérieure est un choix tout à fait raisonnable.

Lorsque j’utilise ST (et d’autres monades), j’essaie de suivre ces directives générales:

• Utilisez souvent le style applicatif . Cela rend le code plus facile à lire et, si vous passez à une version immuable, beaucoup plus facile à convertir. Non seulement cela, mais le style Applicatif est beaucoup plus compact.
• Ne vous contentez pas d’utiliser ST. Si vous programmez uniquement dans ST, le résultat ne sera pas meilleur qu’un programme en C, voire pire à cause des lectures et écritures explicites. Au lieu de cela, intercaler le code Haskell pur où il s’applique. Je me trouve souvent en STRef s (Map k [v]) utiliser des choses comme STRef s (Map k [v]) . La carte elle-même est en cours de mutation, mais une grande partie des opérations lourdes est effectuée purement.
• Ne refait pas les librairies si vous n’avez pas à le faire. Un lot de code écrit pour IO peut être converti proprement et mécaniquement en ST. Remplacer tous les IORef avec STRef et IO avec ST dans Data.HashTable était beaucoup plus facile qu’écrire une implémentation de table de hachage codée à la main, et probablement plus rapide.

Une dernière remarque – si vous rencontrez des problèmes avec les lectures et écritures explicites, il existe des moyens de contourner le problème.

Algorithmes utilisant des mutations et des algorithmes différents des algorithmes. Parfois, il y a une traduction qui préserve les limites de la première à la seconde, parfois difficile, et parfois une seule qui ne préserve pas les limites de la complexité.

Un survol du document me révèle que je ne pense pas que cela fasse un usage essentiel de la mutation – et je pense donc qu’un algorithme fonctionnel paresseux, potentiellement très astucieux, pourrait être développé. Mais ce serait un algorithme différent mais lié à celui décrit.

Ci-dessous, je décris une telle approche – pas nécessairement la meilleure ou la plus intelligente, mais plutôt simple:

Voici la configuration que je comprends – A) un arbre de twigment est construit B) les gains sont ensuite repoussés des feuilles à la racine, ce qui indique le meilleur choix à chaque étape. Mais cela coûte cher. Au lieu de cela, seules des portions de l’arbre sont explorées sur les feuilles de manière non déterministe. De plus, chaque exploration ultérieure de l’arbre est déterminée par ce qui a été appris lors des explorations précédentes.

Nous construisons donc du code pour décrire l’arbre “par étapes”. Ensuite, nous avons une autre structure de données pour définir un arbre partiellement exploré avec des estimations de récompense partielles. Nous avons alors une fonction de randseed -> ptree -> ptree qui donne une graine aléatoire et un arbre partiellement exploré, entreprend une autre exploration de l’arbre, mettant à jour la structure de ptree au fur et à mesure. Ensuite, nous pouvons simplement itérer cette fonction sur un ptree de graine vide pour obtenir une liste d’espaces de plus en plus échantillonnés dans le ptree. Nous pouvons alors parcourir cette liste jusqu’à ce qu’une condition de coupure spécifiée soit remplie.

Donc, maintenant, nous sums passés d’un algorithme où tout est mélangé à trois étapes distinctes: 1) construire l’arborescence complète, paresseusement, 2) mettre à jour une exploration partielle avec un échantillonnage d’une structure et 3) décider quand nous avons recueilli suffisamment d’échantillons.

Il peut être très difficile de savoir quand utiliser ST est approprié. Je vous suggère de le faire avec ST et sans ST (pas nécessairement dans cet ordre). Gardez la version non-ST simple; L’utilisation de ST doit être considérée comme une optimisation, et vous ne voulez pas le faire tant que vous n’en avez pas besoin.

Je dois admettre que je ne peux pas lire le code Haskell. Mais si vous utilisez ST pour muter l’arbre, vous pouvez probablement le remplacer par un arbre immuable sans perdre beaucoup car:

Même complexité pour les arbres mutables et immuables

Vous devez muter chaque nœud au-dessus de la nouvelle feuille. Un arbre immuable doit remplacer tous les nœuds au-dessus du nœud modifié. Dans les deux cas, les nœuds touchés sont les mêmes, vous ne gagnez donc rien en complexité.

Par exemple, la création d’objects Java est plus coûteuse que la mutation, alors peut-être que vous pouvez gagner un peu ici en utilisant la mutation. Mais cela je ne sais pas avec certitude. Mais un petit gain ne vous achète pas beaucoup à cause du prochain point.

La mise à jour de l’arbre n’est probablement pas le goulot d’étranglement

L’évaluation de la nouvelle feuille sera probablement beaucoup plus coûteuse que la mise à jour de l’arborescence. C’est du moins le cas pour UCT dans l’ordinateur Go.

L’utilisation de la monade ST est généralement (mais pas toujours) une optimisation. Pour toute optimisation, j’applique la même procédure:

1. Écrivez le code sans lui,
2. Profil et identifier les goulots d’étranglement,
3. Réécrire progressivement les goulots d’étranglement et tester les améliorations / régressions,

L’autre cas d’utilisation que je connais est une alternative à la monade d’état. La principale différence est que, avec la monade d’état, le type de toutes les données stockées est spécifié de manière descendante, tandis que la monade ST est spécifiée de bas en haut. Il y a des cas où cela est utile.