Motif de conception? Fonction d'itération dans une liste à la recherche du premier résultat {succès}

Question

J'ai un problème de codage dans Erlang qui est probablement un modèle de conception commun, mais je ne trouve aucune information sur la façon de le résoudre.

J'ai une liste L. Je veux appliquer une fonction f à chaque élément de L, et l'exécuter simultanément sur tous les éléments de L. Chaque appel à f (élément) réussira ou échouera; dans la majorité des cas, il échouera, mais occasionnellement il réussira pour un élément spécifique au sein de L.

Si/quand af (Element) réussit, je veux retourner "succès" et terminer toutes les invocations de f pour D'autres éléments dans L - le premier "succès" est tout ce qui m'intéresse. D'un autre côté, si f (Element) échoue pour chaque élément dans L, alors je veux retourner "fail". Supposons que L soit une liste d'entiers, et F renvoie {succès} si un élément de L est 3 ou {échec} pour toute autre valeur. Je veux trouver le plus rapidement possible s'il y a des 3 dans L; Je me fiche du nombre de 3, juste si au moins un 3 existe ou non. f pourrait ressembler à ceci:

f(Int) -> 
    case Int of 
    3 -> {success}; 
    _ -> {fail} 
    end. 

Comment puis-je itérer une liste de Ints pour savoir si la liste contient au moins un 3, et revenir le plus rapidement possible?

Assurément, c'est un modèle de conception fonctionnelle commune, et je ne suis pas en utilisant les termes de recherche de Google ...

Answer 1

Comme cela a déjà été répondu, votre solution consiste à utiliser des listes: any/2.

Voyant que vous voulez une version concurrente de celle-ci:

any(F, List) -> 
    Parent = self(), 
    Pid = spawn(fun() -> spawner(Parent, F, List) end), 
    receive {Pid, Result} -> Result 
    end, 
    Result. 

spawner(Parent, F, List) -> 
    Spawner = self(), 
    S = spawn_link(fun() -> wait_for_result(Spawner, Parent, length(List)) end), 
    [spawn_link(fun() -> run(S, F) end) || X <- List], 
    receive after infinity -> ok end. 

wait_for_result(Spawner, Parent, 0) -> 
    Parent ! {Spawner, false}, 
    exit(have_result); 
wait_for_result(Spawner, Parent, Children) -> 
    receive 
    true -> Parent ! {Spawner, true}, exit(have_result); 
    false -> wait_for_result(Spawner, Parent, Children -1) 
    end. 

run(S, F) -> 
    case catch(F()) of 
    true -> S ! true; 
    _ -> S ! false 
    end. 

Notez que tous les enfants (les processus « run ») vont mourir lorsque le processus de « wait_for_children » fait une sortie (have_result). Entièrement non testé ... Ah, que diable. Je vais faire un exemple:

4> play:any(fun(A) -> A == a end, [b,b,b,b,b,b,b,b]). 
false 
5> play:any(fun(A) -> A == a end, [b,b,b,b,b,b,a,b]). 
true 

Il pourrait encore y avoir des bogues (et il y en a probablement).

Answer 2

Il fondamentalement deux façons différentes de le faire. Soit écrire votre propre fonction qui effectue une itération sur la liste retour true ou false selon que l'on trouve un 3:

contains_3([3|_]) -> true; 
contains_3([_|T]) -> contains_3(T); 
contains_3([]) -> false. 

La seconde est d'utiliser une fonction déjà définie pour faire l'itération réelle jusqu'à ce qu'un test sur les éléments de la liste est vrai et lui fournir le test. lists:any retours true ou false selon que le test réussit au moins un élément:

contains_3(List) -> lists:any(fun (E) -> E =:= 3 end, List). 

fera la même chose. Ce que vous choisissez est à vous. Le second serait probablement plus proche d'un modèle de conception mais je pense que même si vous l'utilisez, vous devriez avoir une idée de comment cela fonctionne en interne. Dans ce cas, il est trivial et très proche du cas explicite.

C'est une chose très commune à faire, mais si elle classerait comme motif de conception je ne sais pas. Cela semble tellement basique et en un sens "trivial" que j'hésiterais à l'appeler un motif de conception.

Answer 3

Cela fait longtemps que je n'ai fait aucun erlang, donc je ne vais pas essayer de vous fournir une syntaxe, cependant erlang et l'OTP ont la solution qui vous attend.

Générer un processus représentant la fonction; faites-le parcourir la liste, en générant autant de processus que vous le jugez approprié pour effectuer le calcul par élément de manière efficace.

Associez chaque processus au processus de fonction et terminez le processus de fonction après avoir renvoyé le premier résultat.

Laisser erlang/otp pour nettoyer le reste des processus.

Answer 4

Vous voudrez peut-être regarder le module plists: http://code.google.com/p/plists/ Bien que je ne sais pas si plists:any poignées

(a) le 1er {succès} a reçu, dire aux autres sous-processus pour arrêter le traitement & quitter ASAP