Ocaml des conseils de mise en œuvre d'un algorithme sur des ensembles

Question

Je rencontre des problèmes pour convertir algo suivants en OCaml Pour mettre en œuvre cet algorithme i utilisé Set.Make(String) foncteur actualy et sortir sont 2 fonctions Quelqu'un peut-il me donner le code percise aide en OCaml pour suivre

Ceci est en fait Algo for Live Variables[PDF] ..Help serait grandement apprécié

for all n, in[n] = out[n] = Ø 
w = { set of all nodes } 
repeat until w empty 
    n = w.pop() 
    out[n] = ∪ n’ ∈ succ [n] in[n’] 
    in[n] = use[n] ∪ (out[n] — def [n]) 
    if change to in[n], 
     for all predecessors m of n, w.push(m) 
end 

Answer 1

for all n, in[n] = out[n] = Ø 
    w = { set of all nodes } 
    repeat until w empty 
    n = w.pop() 
    out[n] = ∪ n’ ∈ succ [n] in[n’] 
    in[n] = use[n] ∪ (out[n] — def [n]) 
    if change to in[n], 
    for all predecessors m of n, w.push(m) 
end 

Il est difficile pour moi de dire ce qui se passe exactement ici. Je pense qu'il y a quelques problèmes d'alignement avec votre texte - repeat until w empty devrait être répéter les 5 prochaines lignes, non? Et comment vont et viennent les fonctions, elles me ressemblent? En dehors de ces déficiences, j'aborderai quelques règles générales que j'ai suivies.

J'ai dû traduire un certain nombre de méthodes numériques dans les algorithmes C et Fortran en langages fonctionnels et j'ai quelques suggestions pour vous.

0) Définir les types de données utilisés. Cela va vraiment vous aider avec la prochaine étape (spoiler: recherche de constructions fonctionnelles). Une fois que vous connaissez les types de données, vous pouvez définir plus précisément les constructions fonctionnelles que vous appliquerez éventuellement.

1) Rechercher des constructions fonctionnelles. fold, récursion, et des cartes, et quand les utiliser. Par exemple, le for all predecessors m est un pli (ne sachant pas s'il se plierait sur un arbre ou une liste, mais pas un pli). While les boucles sont un bon endroit pour la récursivité - mais ne vous inquiétez pas de faire un appel de queue, vous pouvez modifier les paramètres plus tard pour se conformer à ces exigences. Ne vous inquiétez pas d'être pur à 100%. Supprimez suffisamment de constructions impures (références ou tableaux) pour avoir une idée de l'algorithme d'une manière fonctionnelle.

2) Écrivez une partie partie de l'algorithme que vous pouvez. Laissant les fonctions vides, ajoutez des valeurs factices, et mettez en application ce que vous savez - alors vous pouvez demander SO mieux, des questions plus éclairées.

3) Réécrivez-le. Il y a de fortes chances que vous ayez manqué certaines constructions fonctionnelles ou utilisé un tableau ou une référence où vous réalisez maintenant que vous pouvez utiliser une liste ou un ensemble ou en passant un accumulateur. Vous avez peut-être défini une liste, mais plus tard, vous réalisez que vous ne pouvez pas y accéder aléatoirement (bien, ce serait très préjudiciable), ou vous devez la parcourir en avant et en arrière (un bon endroit pour une fermeture à glissière). De toute façon, quand vous l'aurez enfin, vous le saurez, et vous devriez avoir un énorme sourire d'oreille sur votre visage.