Quels sont les équivalents fonctionnels des instructions de rupture impératives et des autres vérifications de boucle?

36

Disons, j'ai la logique ci-dessous. Comment écrire cela dans la programmation fonctionnelle?

    public int doSomeCalc(int[] array)
    {
        int answer = 0;
        if(array!=null)
        {
            for(int e: array)
            {
                answer += e;
                if(answer == 10) break;
                if(answer == 150) answer += 100;
            }
        }
        return answer;
    }

Les exemples dans la plupart des blogs, des articles ... Je vois juste expliquer le cas simple d'une fonction mathématique simple dit «Somme». Mais, j’ai une logique similaire à celle décrite ci-dessus en Java et j’aimerais la migrer vers du code fonctionnel dans Clojure. Si nous ne pouvons pas faire ce qui précède dans FP, le type de promotions pour FP ne l'indique pas explicitement.

Je sais que le code ci-dessus est totalement impératif. Il n'a pas été écrit avec la prévoyance de le migrer vers FP dans le futur.

Vicky
la source
1
Notez que la combinaison de breaket return answerpeut être remplacée par une returnboucle interne. Dans FP, vous pouvez implémenter ce retour rapide en utilisant des continuations, voir par exemple en.wikipedia.org/wiki/Continuation
Giorgio
1
Les continuations de @Giorgio seraient une énorme surcharge ici. De toute façon, c’est une boucle. Pour appeler sa prochaine itération, vous devez effectuer un appel final. Par conséquent, pour rompre, il suffit de ne plus l’appeler et de renvoyer la réponse. Pour les boucles imbriquées , ou tout autre flux de contrôle compliqué, vous pouvez utiliser des continuations au lieu de forcer pour restructurer votre code en utilisant la technique simple ci-dessus (ce qui devrait toujours être possible, mais peut conduire à une structure de code trop complexe qui expliquerait plus ou moins la suite, et pour plus d’un point de sortie, vous en aurez certainement besoin).
Will Ness
8
Dans ce cas: takeWhile.
Jonathan Cast
1
@ WillNess: Je voulais juste le mentionner car il peut être utilisé pour laisser un calcul complexe à tout moment. Ce n'est probablement pas la meilleure solution pour l'exemple concret du PO.
Giorgio
@Giorgio vous avez raison, c'est le plus complet en général. en fait, cette question est très large, IYKWIM (c’est-à-dire qu’elle serait fermée à tout moment par la même occasion).
Will Ness

Réponses:

45

L'équivalent le plus proche du bouclage sur un tableau dans la plupart des langages fonctionnels est une foldfonction, c'est-à-dire une fonction qui appelle une fonction spécifiée par l'utilisateur pour chaque valeur du tableau, en transmettant une valeur accumulée le long de la chaîne. Dans de nombreux langages fonctionnels, folddiverses fonctions supplémentaires, telles que la possibilité d’arrêter plus tôt lorsque survient une condition, viennent s’ajouter à celle-ci. Dans les langages paresseux (par exemple, Haskell), il est possible d’arrêter tôt en évitant d’évaluer la suite de la liste, ce qui évitera de générer des valeurs supplémentaires. Par conséquent, en traduisant votre exemple en Haskell, je l’écrirais ainsi:

doSomeCalc :: [Int] -> Int
doSomeCalc values = foldr1 combine values
  where combine v1 v2 | v1 == 10  = v1
                      | v1 == 150 = v1 + 100 + v2
                      | otherwise = v1 + v2

Découper ceci ligne par ligne au cas où vous ne seriez pas familier avec la syntaxe de Haskell, ceci fonctionne comme suit:

doSomeCalc :: [Int] -> Int

Définit le type de la fonction, accepte une liste d'ints et renvoie un seul int.

doSomeCalc values = foldr1 combine values

Le corps principal de la fonction: argument donné values, return foldr1appelé avec arguments combine(que nous définirons plus bas) et values. foldr1est une variante de la primitive fold qui commence par la pile définie sur la première valeur de la liste (d’où le nom 1de la fonction), puis la combine en utilisant la fonction spécifiée par l'utilisateur de gauche à droite (généralement appelée fold à droite , d'où le rdans le nom de la fonction). Donc, foldr1 f [1,2,3]est équivalent à f 1 (f 2 3)(ou f(1,f(2,3))dans la syntaxe plus conventionnelle C-like).

  where combine v1 v2 | v1 == 10  = v1

Définir la combinefonction locale: il reçoit deux arguments, v1et v2. Quand v1est 10, il revient juste v1. Dans ce cas, la v2 n'est jamais évaluée , la boucle s'arrête ici.

                      | v1 == 150 = v1 + 100 + v2

Sinon, lorsque v1 est égal à 150, ajoute 100 points supplémentaires et ajoute v2.

                      | otherwise = v1 + v2

Et, si aucune de ces conditions n'est vraie, ajoute simplement v1 à v2.

Maintenant, cette solution est quelque peu spécifique à Haskell, car le fait qu'un repli droit se termine si la fonction de combinaison n'évalue pas son second argument est causé par la stratégie d'évaluation paresseuse de Haskell. Je ne connais pas Clojure, mais je crois qu’elle utilise une évaluation stricte. Je pense donc qu’elle devrait disposer d’une foldfonction dans sa bibliothèque standard qui inclut un support spécifique pour la résiliation anticipée. Ceci est souvent appelé foldWhile, foldUntilou similaire.

Un rapide coup d’œil à la documentation de la bibliothèque Clojure suggère qu’elle est un peu différente de la plupart des langages fonctionnels en nommant, et que ce foldn’est pas ce que vous recherchez (c’est un mécanisme plus avancé visant à permettre le calcul parallèle), mais reduceplus directe. équivalent. La fin anticipée se produit si la reducedfonction est appelée dans votre fonction de combinaison. Je ne suis pas sûr à 100% de comprendre la syntaxe, mais je soupçonne que ce que vous recherchez ressemble à ceci:

(reduce 
    (fn [v1 v2]
        (if (= v1 10) 
             (reduced v1)
             (+ v1 v2 (if (= v1 150) 100 0))))
    array)

NB: les deux traductions, Haskell et Clojure, ne sont pas tout à fait correctes pour ce code spécifique; mais ils en donnent l'essentiel - voir la discussion dans les commentaires ci-dessous pour des problèmes spécifiques liés à ces exemples.

Jules
la source
11
les noms v1 v2sont déroutants: v1est une "valeur de tableau", mais v2est le résultat accumulé. et votre traduction est erronée, je crois, les sorties de boucle OP lorsque le cumul (à gauche) la valeur montres 10, pas un élément du tableau. Idem avec l’augmentation de 100. Si vous utilisez les plis ici, utilisez le pli gauche avec sortie anticipée, avec quelques variations par rapport à foldlWhile ici .
Will Ness
2
il est amusant de voir comment la réponse la plus fausse obtient le plus de votes positifs sur SE .... c’est bien de faire des erreurs, vous êtes en bonne compagnie :) , aussi. Mais le mécanisme de découverte de connaissances sur SO / SE est définitivement brisé.
Will Ness
1
Le code Clojure est presque correct, mais la condition (= v1 150)utilise la valeur avant v2(ou. e) Lui est ajoutée .
NikoNyrh
1
Breaking this down line by line in case you're not familiar with Haskell's syntax-- Tu es mon héros. Haskell est un mystère pour moi.
Captain Man
15
@ WillNess Il est voté parce que c'est la traduction et l'explication les plus compréhensibles. Le fait que ce soit faux est une honte mais relativement peu importante ici car les petites erreurs n’annulent pas le fait que la réponse est par ailleurs utile. Mais bien sûr, cela devrait être corrigé.
Konrad Rudolph
33

Vous pouvez facilement le convertir en récursivité. Et il a beau appel récursif queue-optimisé.

Pseudocode:

public int doSomeCalc(int[] array)
{
    return doSomeCalcInner(array, 0);
}

public int doSomeCalcInner(int[] array, int answer)
{
    if (array is empty) return answer;

    // not sure how to efficiently implement head/tails array split in clojure
    var head = array[0] // first element of array
    var tail = array[1..] // remainder of array

    answer += head;
    if (answer == 10) return answer;
    if (answer == 150) answer += 100;

    return doSomeCalcInner(tail, answer);
}
Euphorique
la source
14
Oui. L'équivalent fonctionnel d'une boucle est la récursion finale et l'équivalent fonctionnel d'un conditionnel est toujours un conditionnel.
Jörg W Mittag
4
@ JörgWMittag Je dirais plutôt que la récursion de la queue est l'équivalent fonctionnel de GOTO. (Pas si mal, mais quand même assez gênant.) L'équivalent d'une boucle, comme dit Jules, est un pli approprié.
gauche du
6
@leftaroundabout Je ne suis pas du tout d'accord. Je dirais que la récursion de la queue est plus contrainte qu'un goto, étant donné la nécessité de sauter à lui-même et uniquement en position de queue. Cela équivaut fondamentalement à une construction en boucle. Je dirais que récursivité équivaut en général à GOTO. Dans tous les cas, lorsque vous compilez la récursion de la queue, cela revient généralement à une while (true)boucle avec le corps de la fonction dans lequel le retour anticipé n'est qu'une breakdéclaration. Un pli, bien que vous ayez raison de dire qu'il s'agit d'une boucle, est en réalité plus contraint qu'une construction en boucle générale; cela ressemble plus à une boucle pour-chaque
J_mie6
1
@ J_mie6 la raison pour laquelle je considère la récursion finale comme étant plutôt GOTOque vous devez faire une comptabilité fastidieuse de quels arguments dans quel état sont passés à l'appel récursif, pour s'assurer qu'il se comporte réellement comme prévu. Cela n’est pas nécessaire dans la même mesure dans les boucles impératives écrites avec décence (où sont clairement définies les variables avec état et comment elles changent à chaque itération), ni dans la récursion naïve (où l’on ne fait généralement pas grand chose avec les arguments). le résultat est assemblé de manière assez intuitive). ...
partir du
1
... Pour ce qui est des plis: vous avez raison, un pli traditionnel (catamorphisme) est un type de boucle très spécifique, mais ces schémas de récurrence peuvent être généralisés (ana- / apo- / hylomorphismes); collectivement, il s’agit de l’OMI qui remplace adéquatement les boucles impératives.
gauche du
13

J'aime beaucoup la réponse de Jules , mais je voulais aussi souligner quelque chose qui manque souvent à la programmation fonctionnelle paresseuse, à savoir que tout ne doit pas forcément être "dans la boucle". Par exemple:

baseSums = scanl (+) 0

offsets = scanl (\offset sum -> if sum == 150 then offset + 100 else offset) 0

zipWithOffsets xs = zipWith (+) xs (offsets xs)

stopAt10 xs = if 10 `elem` xs then 10 else last xs

result = stopAt10 . zipWithOffsets . baseSums

result [1..]         -- 10
result [11..1000000] -- 500000499945

Vous pouvez voir que chaque partie de votre logique peut être calculée dans une fonction distincte puis composée ensemble. Cela permet des fonctions plus petites, qui sont généralement beaucoup plus faciles à résoudre. Pour votre exemple de jouet, cela ajoute peut-être plus de complexité qu’il n’en supprime, mais dans le code du monde réel, les fonctions de séparation sont souvent beaucoup plus simples que l’ensemble.

Karl Bielefeldt
la source
la logique est dispersée partout ici. ce code ne sera pas facile à maintenir. stopAt10n'est pas un bon consommateur. votre réponse est meilleure que celle que vous citez, car elle isole correctement le producteur scanl (+) 0de base de valeurs. leur consommation devrait incorporer directement la logique de contrôle, cependant, il vaut mieux la mettre en œuvre avec seulement deux spansecondes et un last, explicitement. cela suivrait de près la structure et la logique du code original et serait facile à maintenir.
Will Ness
6

La plupart des exemples de traitement de la liste , vous verrez des fonctions d'utilisation comme map, filter, sumetc. , qui fonctionnent sur la liste dans son ensemble. Mais dans votre cas, vous avez une sortie anticipée conditionnelle - un modèle plutôt inhabituel qui n'est pas pris en charge par les opérations de liste habituelles. Vous devez donc définir un niveau d'abstraction et utiliser la récursivité, ce qui est également plus proche de la présentation de l'exemple impératif.

Ceci est une traduction plutôt directe (probablement pas idiomatique) de Clojure:

(defn doSomeCalc 
  ([lst] (doSomeCalc lst 0))
  ([lst sum]
    (if (empty? lst) sum
        (if (= sum 10) sum
            (let [sum (+ sum (first lst))]
                 [sum (if (= sum 150) (+ sum 100) sum)]
               (recur (rest lst) sum))))))) 

Edit: Jules fait remarquer qu’à reduceClojure , les sorties anticipées sont possibles. Utiliser ceci est plus élégant:

(defn doSomeCalc [lst]  
  (reduce (fn [sum val]
    (if (= sum 10) (reduced sum)
        (let [sum (+ sum val)]
             [sum (if (= sum 150) (+ sum 100) sum)]
           sum))
   lst)))

Dans tous les cas, vous pouvez faire n'importe quoi dans des langages fonctionnels comme dans des langages impératifs, mais vous devez souvent changer quelque peu votre mental pour trouver une solution élégante. Dans le codage impératif, vous pensez traiter une liste étape par étape, tandis que dans les langages fonctionnels, vous recherchez une opération à appliquer à tous les éléments de la liste.

JacquesB
la source
voir la modification que je viens d'ajouter à ma réponse: l' reduceopération de Clojure prend en charge les sorties anticipées.
Jules le
@Jules: Cool - c'est probablement une solution plus idiomatique.
JacquesB
Incorrect - ou n'est takeWhilepas une «opération commune»?
Jonathan Cast
@jcast - Bien que ce takeWhilesoit une opération courante, ce n'est pas particulièrement utile dans ce cas, car vous avez besoin des résultats de votre transformation avant de pouvoir décider d'arrêter ou non. Dans un langage paresseux, cela n'a pas d'importance: vous pouvez utiliser scanet takeWhilesur les résultats de l'analyse (voir la réponse de Karl Bielefeldt, qui, bien qu'il ne l'utilise pas, takeWhilepourrait facilement être réécrite pour le faire), mais pour un langage strict comme clojure, signifie traiter toute la liste et ensuite éliminer les résultats. Les fonctions de générateur pourraient toutefois résoudre ce problème, et je pense que clojure les prend en charge.
Jules
@Jules take-whilein Clojure produit une séquence lente (selon la documentation). Une autre façon de résoudre ce problème serait d'utiliser des transducteurs (peut-être le meilleur).
Will Ness
4

Comme le soulignent d’autres réponses, Clojure doit, reducedpour arrêter les réductions à un stade précoce:

(defn some-calc [coll]
  (reduce (fn [answer e]
            (let [answer (+ answer e)]
               (case answer
                 10  (reduced answer)
                 150 (+ answer 100)
                 answer)))
          0 coll))

C'est la meilleure solution pour votre situation particulière. Vous pouvez également obtenir beaucoup de temps en combinant reducedavec transduce, ce qui vous permet d'utiliser des transducteurs map, filteretc. Cependant, la réponse à votre question générale est loin d'être complète.

Les suites d'échappement sont une version généralisée des instructions break et return. Ils sont directement implémentés dans certains Schemes ( call-with-escape-continuation), Common Lisp ( block+ return, catch+ throw) et même C ( setjmp+ longjmp). Des suites plus générales délimitées ou non délimitées, telles que définies dans le schéma standard ou comme monades de continuation dans Haskell et Scala, peuvent également être utilisées en tant que suites d'échappement.

Par exemple, dans Racket, vous pourriez utiliser let/eccomme ceci:

(define (some-calc ls)
  (let/ec break ; let break be an escape continuation
    (foldl (lambda (answer e)
             (let ([answer (+ answer e)])
               (case answer
                 [(10)  (break answer)] ; return answer immediately
                 [(150) (+ answer 100)]
                 [else  answer])))
           0 ls)))

De nombreux autres langages ont également des constructions de type continuation, sous forme de gestion des exceptions. En Haskell, vous pouvez également utiliser l'une des différentes monades d'erreur foldM. Parce qu’il s’agit principalement de structures de traitement des erreurs utilisant des exceptions ou des monades d’erreur pour les retours anticipés, elles sont généralement inacceptables du point de vue culturel et peuvent être très lentes.

Vous pouvez également passer des fonctions d’ordre supérieur aux appels en attente.

Lorsque vous utilisez des boucles, vous entrez automatiquement la prochaine itération lorsque vous atteignez la fin du corps de la boucle. Vous pouvez entrer tôt la prochaine itération avec continueou quitter la boucle avec break(ou return). Lorsque vous utilisez des appels de queue (ou la loopconstruction de Clojure qui imite la récursion de queue), vous devez toujours effectuer un appel explicite pour entrer l'itération suivante. Pour arrêter la lecture en boucle, ne passez pas l'appel récursif, mais donnez directement la valeur:

(defn some-calc [coll]
  (loop [answer 0, [e es :as coll] coll]
    (if (empty? coll)
      answer
      (let [answer (+ answer e)]
        (case answer
          10 answer
          150 (recur (+ answer 100) es)
          (recur answer es))))))
nilern
la source
1
En ce qui concerne l’utilisation des monades sur les erreurs à Haskell, je ne pense pas que les performances soient réellement pénalisées. Ils ont tendance à penser à la gestion des exceptions, mais ils ne fonctionnent pas de la même manière et aucune pile n’est requise, donc ne devrait vraiment pas être un problème si elle était utilisée de cette façon. En outre, même s'il existe une raison culturelle de ne pas utiliser quelque chose du genre MonadError, l'équivalent en substance Eithern'a pas un tel parti pris pour la gestion des erreurs uniquement, et peut donc facilement être utilisé à la place.
Jules
@Jules, je pense que le retour à gauche n'empêche pas le pli de parcourir la liste complète (ou une autre séquence). Pas très familier avec les composants internes de la bibliothèque standard Haskell.
Nilern
2

La partie complexe est la boucle. Commençons par cela. Une boucle est généralement convertie en style fonctionnel en exprimant l'itération avec une seule fonction. Une itération est une transformation de la variable de boucle.

Voici une implémentation fonctionnelle d'une boucle générale:

loop : v -> (v -> v) -> (v -> Bool) -> v
loop init iter cond_to_cont = 
    if cond_to_cont init 
        then loop (iter init) iter cond
        else init

Cela prend (une valeur initiale de la variable de boucle, la fonction qui exprime une seule itération [sur la variable de boucle]) (une condition pour continuer la boucle).

Votre exemple utilise une boucle sur un tableau, qui se casse également. Cette capacité dans votre langue impérative est incorporée dans la langue elle-même. En programmation fonctionnelle, une telle capacité est généralement implémentée au niveau de la bibliothèque. Voici une implémentation possible

module Array (foldlc) where

foldlc : v -> (v -> e -> v) -> (v -> Bool) -> Array e -> v
foldlc init iter cond_to_cont arr = 
    loop 
        (init, 0)
        (λ (val, next_pos) -> (iter val (at next_pos arr), next_pos + 1))
        (λ (val, next_pos) -> and (cond_to_cont val) (next_pos < size arr))

En cela:

J'utilise une paire ((val, next_pos)) qui contient la variable de boucle visible à l'extérieur et la position dans le tableau, que cette fonction cache.

La fonction d'itération est légèrement plus complexe que dans la boucle générale, cette version permet d'utiliser l'élément courant du tableau. [Il est sous forme de curry .]

De telles fonctions sont généralement appelées "fold".

Je mets un "l" dans le nom pour indiquer que l'accumulation des éléments du tableau se fait de manière associative à gauche; imiter l'habitude des langages de programmation impératifs pour itérer un tableau d'index faible à élevé.

Je mets un "c" dans le nom pour indiquer que cette version de fold prend une condition qui contrôle si et quand la boucle doit être arrêtée plus tôt.

Bien entendu, ces fonctions utilitaires sont susceptibles d'être facilement disponibles dans la bibliothèque de base livrée avec le langage de programmation fonctionnel utilisé. Je leur ai écrit ici pour démonstration.

Maintenant que nous avons tous les outils qui sont dans la langue dans le cas impératif, nous pouvons à présent mettre en œuvre les fonctionnalités spécifiques de votre exemple.

La variable dans votre boucle est une paire ('answer', un booléen qui indique s'il faut continuer).

iter : (Int, Bool) -> Int -> (Int, Bool)
iter (answer, cont) collection_element = 
  let new_answer = answer + collection_element
  in case new_answer of
    10 -> (new_answer, false)
    150 -> (new_answer + 100, true)
    _ -> (new_answer, true)

Notez que j'ai utilisé une nouvelle "variable" 'new_answer'. En effet, en programmation fonctionnelle, je ne peux pas changer la valeur d'une "variable" déjà initialisée. Je ne m'inquiète pas des performances, le compilateur pourrait réutiliser la mémoire de 'answer' pour 'new_answer' via une analyse à vie, s'il pense que cela est plus efficace.

En incorporant cela dans notre fonction de boucle développée précédemment:

doSomeCalc :: Array Int -> Int
doSomeCalc arr = fst (Array.foldlc (0, true) iter snd arr)

"Array" est le nom du module qui exporte la fonction foldlc.

"poing", "deuxième" représente les fonctions qui retournent la première, deuxième composante de son paramètre de paire

fst : (x, y) -> x
snd : (x, y) -> y

Dans ce cas, le style "sans point" augmente la lisibilité de l'implémentation de doSomeCalc:

doSomeCalc = Array.foldlc (0, true) iter snd >>> fst

(>>>) est la composition de la fonction: (>>>) : (a -> b) -> (b -> c) -> (a -> c)

C'est la même chose que ci-dessus, juste le paramètre "arr" est omis des deux côtés de l'équation qui définit.

Une dernière chose: vérifier la casse (array == null). Dans des langages de programmation mieux conçus, mais même dans des langages mal conçus avec une discipline de base, on utilise plutôt un type optionnel pour exprimer la non-existence. Cela n’a pas grand-chose à voir avec la programmation fonctionnelle, qui est au coeur de la question, donc je ne la traite pas.

libeako
la source
0

Tout d’abord, réécrivez légèrement la boucle, de sorte que chaque itération de la boucle se termine tôt ou mute answerexactement une fois:

    public int doSomeCalc(int[] array)
    {
        int answer = 0;
        if(array!=null)
        {
            for(int e: array)
            {
                if(answer + e == 10) return answer + e;
                else if(answer + e == 150) answer = answer + e + 100;
                else answer = answer + e;
            }
        }
        return answer;
    }

Il devrait être clair que le comportement de cette version est exactement le même qu'auparavant, mais maintenant, il est beaucoup plus simple de convertir en style récursif. Voici une traduction directe en Haskell:

doSomeCalc :: [Int] -> Int
doSomeCalc = recurse 0
  where recurse :: Int -> [Int] -> Int
        recurse answer [] = answer
        recurse answer (e:array)
          | answer + e == 10 = answer + e
          | answer + e == 150 = recurse (answer + e + 100) array
          | otherwise = recurse (answer + e) array

Désormais, il est purement fonctionnel, mais nous pouvons l’améliorer à la fois en termes d’efficacité et de lisibilité en utilisant un repli au lieu d’une récursion explicite:

import Control.Monad (foldM)

doSomeCalc :: [Int] -> Int
doSomeCalc = either id id . foldM go 0
  where go :: Int -> Int -> Either Int Int
        go answer e
          | answer + e == 10 = Left (answer + e)
          | answer + e == 150 = Right (answer + e + 100)
          | otherwise = Right (answer + e)

Dans ce contexte, les Leftsorties prématurées avec sa valeur et Rightla récursion continue avec sa valeur.


Cela pourrait maintenant être simplifié un peu plus, comme ceci:

import Control.Monad (foldM)

doSomeCalc :: [Int] -> Int
doSomeCalc = either id id . foldM go 0
  where go :: Int -> Int -> Either Int Int
        go answer e
          | answer' == 10 = Left 10
          | answer' == 150 = Right 250
          | otherwise = Right answer'
          where answer' = answer + e

C'est mieux en tant que code Haskell final, mais la façon dont il est renvoyé au Java d'origine est maintenant un peu moins claire.

Joseph Sible-Réintégrer Monica
la source