ST Monade == odeur de code?

Question

Je suis en train de travailler sur la mise en œuvre de l' UCT algorithme en Haskell, ce qui nécessite une quantité considérable de données de jonglage. Sans entrer dans trop de détails, c'est un algorithme de simulation où, à chaque "étape", un nœud feuille dans l'arbre de recherche est sélectionné en fonction de certaines propriétés statistiques, un nouveau nœud enfant est construit à que les feuilles, et les statistiques correspondant à la nouvelle feuille et tous ses ancêtres sont mis à jour.

Compte tenu de tout ce que la jonglerie, je ne suis pas assez forte pour comprendre comment faire de l'ensemble de l'arbre de recherche une belle immuable structure de données à la Okasaki. Au lieu de cela, j'ai été jouer avec l' ST monade un peu, la création de structures composées de mutable STRefs. Un exemple artificiel (sans rapport avec l'UCT):

import Control.Monad
import Control.Monad.ST
import Data.STRef

data STRefPair s a b = STRefPair { left :: STRef s a, right :: STRef s b }

mkStRefPair :: a -> b -> ST s (STRefPair s a b)
mkStRefPair a b = do
    a' <- newSTRef a
    b' <- newSTRef b
    return $ STRefPair a' b'

derp :: (Num a, Num b) => STRefPair s a b -> ST s ()
derp p = do
    modifySTRef (left p) (\x -> x + 1)
    modifySTRef (right p) (\x -> x - 1)

herp :: (Num a, Num b) => (a, b)
herp = runST $ do
    p <- mkStRefPair 0 0
    replicateM_ 10 $ derp p
    a <- readSTRef $ left p
    b <- readSTRef $ right p
    return (a, b)

main = print herp -- should print (10, -10)

Évidemment, cet exemple en particulier, serait beaucoup plus facile d'écrire sans l'aide d' ST, mais j'espère que c'est clair là où je veux en venir... si je devais appliquer ce genre de style à mon UCT cas d'utilisation, c'est que de l'entêtement?

Quelqu'un a posé une question similaire ici une couple d'années en arrière, mais je pense que ma question est un peu différent... je n'ai pas de problème à l'aide de monades pour encapsuler mutable état lorsque cela est approprié, mais c'est que "lorsque cela est approprié, une clause" qui me fait. Je suis inquiet que je suis en train de revenir à un état d'esprit orienté objet prématurément, où j'ai un tas d'objets avec des getters et setters. Pas exactement idiomatiques Haskell...

D'autre part, s'il est raisonnable de style de codage pour un ensemble de problèmes, je suppose que ma question devient: est-il bien connu des façons de garder ce genre de code lisible et maintenable? Je suis un peu dégoûtés par tous les explicite les lectures et les écritures, et en particulier dégoûtés par avoir à traduire à partir de mon STRef-les structures à l'intérieur de l' ST monade à isomorphe mais immuable structures à l'extérieur.

Answer 1

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

• Il y a déjà bien connue, des moyens efficaces pour résoudre un problème. Quicksort est un parfait exemple de cela. Il est connu pour sa vitesse et le comportement, ce qui ne peut être imité par pur code très bien.
• Vous avez besoin rigide temps et de l'espace de limites. Surtout avec l'évaluation différée (et Haskell n'a même pas de préciser s'il est paresseux de l'évaluation, c'est juste que c'est non stricte), le comportement de vos programmes peuvent être très imprévisibles. Si il y a une fuite de mémoire pourraient dépendre de l'existence d'une certaine optimisation est activée. C'est très différent de code impératif, qui dispose d'un ensemble fixe de variables (en général) et d'évaluation définies commande.
• Vous avez une date limite. Bien que le pur style est presque toujours une meilleure pratique et plus propre code, si vous êtes habitué à l'écriture impérativement besoin et le code bientôt, départ impératif et le mouvement fonctionnel, le plus tard est parfaitement raisonnable de choix.

Lorsque je fais un SAINT (et d'autres monades), j'essaie de suivre ces lignes directrices:

• Utilisation Applicative style souvent. Cela rend le code plus facile à lire et, si vous le faites passer à un immuable version, beaucoup plus facile à convertir. Non seulement cela, mais Applicative style est beaucoup plus compact.
• Ne vous contentez pas utiliser de ST. Si vous programmez seulement en ST, le résultat sera pas mieux qu'un vaste programme C, éventuellement, de pire en raison de l'explicite en lecture et en écriture. Au lieu de cela, parsemer de pur code Haskell où il s'applique. Je me retrouve souvent en utilisant des choses comme STRef s (Map k [v]). La carte elle-même est en train d'être muté, mais le gros du travail est fait purement.
• Ne pas refaire les bibliothèques si vous n'avez pas à. Beaucoup de code écrit pour IO peut être proprement, et assez mécaniquement, converti à ST. Le remplacement de tous les IORefs avec STRefs et IOs à STs dans les Données.Table de hachage a été beaucoup plus facile que d'écrire un codés à la main la table de hachage de la mise en œuvre aurait été, et probablement plus rapide aussi.

Une dernière remarque: si vous rencontrez des problèmes avec le explicite les lectures et les écritures, il y a des façons de contourner cela.

Answer 2

Les algorithmes qui font usage de la mutation et des algorithmes qui ne sont pas différents algorithmes. Il y a parfois un strightforward limites de la préservation de la traduction de la première à la seconde, parfois difficile, et parfois un seul qui ne permet pas de conserver la complexité de limites.

Une écrémé de l'article montre pour moi que je ne pense pas que cela rend indispensable l'utilisation de mutation, et donc je pense que potentiellement vraiment chouette paresseux fonctionnel de l'algorithme pourrait être développé. Mais ce serait une différents, mais liés algorithme que celui décrit.

Ci-dessous, je décris une telle approche -- pas nécessairement le meilleur, ni le plus intelligent, mais assez simple:

Voici la configuration d'un je comprends bien -- A) une ramification de l'arbre est construit B) les paiements sont alors repoussés de la pousse des feuilles à la racine qui indique alors le meilleur choix à une étape donnée. Mais c'est cher, donc au lieu de cela, uniquement les parties de l'arbre sont explorées pour les leafs dans une manière non déterministe. En outre, chaque poursuite de l'exploration de l'arbre est déterminée par ce qui a été appris dans les explorations précédentes.

Donc, nous construisons code pour décrire le "stade-sage" de l'arbre. Ensuite, nous avons une autre structure de données pour définir un partiellement explorées arbre le long partielle de la récompense des estimations. Nous avons alors une fonction d' randseed -> ptree -> ptree que donné une valeur aléatoire et partiellement exploré arbre, se lance dans une poursuite de l'exploration de l'arbre, la mise à jour de la ptree structure que nous allons. Ensuite, il nous suffit de parcourir cette fonction sur un vide de semences ptree pour obtenir une liste de plus en plus échantillonné des espaces dans le ptree. Ensuite nous pouvons marcher sur cette liste jusqu'à ce que certains de coupure spécifiée condition est remplie.

Alors maintenant, nous sommes passés d'un algorithme où tout est mélangé à trois étapes distinctes -- 1) la construction de l'ensemble de l'état de l'arbre, paresseusement, 2) la mise à jour de certains exploration partielle de certains échantillons d'une structure et d'3) de décider quand nous avons rassemblé assez d'échantillons.

Answer 3

Il peut être vraiment difficile à dire lors de l'utilisation de ST est approprié. Je vous suggère de le faire avec ST et sans ST (pas nécessairement dans cet ordre). Garder le non-ST version simple; à l'aide de la ST devrait être considérée comme une optimisation, et vous ne voulez pas le faire jusqu'à ce que vous savez vous en avez besoin.

Answer 4

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

1. Écrire le code sans elle,
2. Profil et identifier les goulots d'étranglement,
3. Progressivement réécrire les goulots d'étranglement et de test pour les améliorations et les régressions,

Les autres cas d'utilisation que je connaisse est comme une alternative à l'état de monade. La principale différence étant que, avec l'état de monade le type de toutes les données stockées est spécifié dans un top-down, tandis qu'avec la ST monade il est précisé bottom-up. Il y a des cas où c'est utile.

Answer 5

Je dois avouer que je ne peut pas lire le code Haskell. Mais si vous utilisez ST pour la mutation de l'arbre, alors vous pouvez probablement la remplacer par une immuable arbre sans perdre beaucoup de raison:

Même complexité pour mutable et immuable de l'arbre

Vous avez à muter chaque nœud au-dessus de la nouvelle feuille. Immuable arbre a remplacer tous les nœuds au-dessus de la modification de nœud. Dans les deux cas, le touché les nœuds sont les mêmes, donc vous n'avez pas gagner quoi que ce soit dans la complexité.

Pour, par exemple, Java création d'un objet est plus cher que la mutation, alors peut-être vous pouvez acquérir un peu ici en Haskell par l'aide de la mutation. Mais ce que je ne sais pas pour sûr. Mais un petit gain ne pas vous acheter beaucoup, parce que du point suivant.

La mise à jour de l'arbre est sans doute pas le goulot d'étranglement

L'évaluation de la nouvelle feuille de route sera probablement beaucoup plus cher que la mise à jour de l'arbre. Au moins c'est le cas pour l'UCT dans l'ordinateur d'Aller.