Quali sono gli equivalenti funzionali delle istruzioni di interruzione imperativa e di altri controlli di ciclo?

L'equivalente più vicino al loop su un array nella maggior parte dei linguaggi funzionali è una funzione fold , cioè una funzione che chiama una funzione specificata dall'utente per ciascun valore dell'array, passando un valore accumulato lungo la catena. In molti linguaggi funzionali, fold è potenziato da una serie di funzioni aggiuntive che forniscono funzionalità extra, inclusa l'opzione di interrompere anticipatamente quando si verificano alcune condizioni. Nelle lingue lazy (ad esempio Haskell), l'arresto anticipato può essere ottenuto semplicemente non valutando ulteriormente lungo l'elenco, il che causerà la generazione di valori aggiuntivi. Pertanto, traducendo il tuo esempio in Haskell, lo scriverei come:

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

Rompendo questo punto per riga nel caso in cui non si abbia familiarità con la sintassi di Haskell, questo funziona in questo modo:

doSomeCalc :: [Int] -> Int

Definisce il tipo di funzione, accettando un elenco di int e restituendo un singolo int.

doSomeCalc values = foldr1 combine values

Il corpo principale della funzione: argomento dato values , return foldr1 chiamato con argomenti combine (che definiremo di seguito) e values . foldr1 è una variante della primitiva piega che inizia con l'accumulatore impostato sul primo valore della lista (da cui la 1 nel nome della funzione), quindi combina usando la funzione specificata dall'utente da sinistra a destra (che è di solito chiamato right fold , quindi r nel nome della funzione). Quindi foldr1 f [1,2,3] equivale a f 1 (f 2 3) (o f(1,f(2,3)) nella sintassi più simile a C).

  where combine v1 v2 | v1 == 10  = v1

Definizione della funzione locale combine : riceve due argomenti, v1 e v2 . Quando v1 è 10, restituisce solo v1 . In questo caso, v2 non viene mai valutato , quindi il loop si ferma qui.

                      | v1 == 150 = v1 + 100 + v2

In alternativa, quando v1 è 150, aggiunge 100 extra e aggiunge v2.

                      | otherwise = v1 + v2

E, se nessuna di queste condizioni è vera, basta aggiungere v1 alla v2.

Ora, questa soluzione è in qualche modo specifica per Haskell, perché il fatto che un fold a destra termina se la funzione di combinazione non valuta il suo secondo argomento è causato dalla strategia di valutazione pigra di Haskell. Non conosco Clojure, ma credo che utilizzi una valutazione rigorosa, quindi mi aspetterei che avesse una funzione fold nella sua libreria standard che include il supporto specifico per la terminazione anticipata. Questo è spesso chiamato foldWhile , foldUntil o simile.

Un rapido sguardo alla documentazione della libreria Clojure suggerisce che è un po 'diverso dalla maggior parte dei linguaggi funzionali nella denominazione, e che fold non è quello che stai cercando (è un meccanismo più avanzato volto a consentire il calcolo parallelo ) ma reduce è l'equivalente più diretto. La terminazione anticipata si verifica se la funzione reduced viene chiamata all'interno della funzione di combinazione. Non sono sicuro al 100% di aver compreso la sintassi, ma sospetto che quello che stai cercando sia qualcosa del genere:

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

NB: entrambe le traduzioni, Haskell e Clojure, non sono corrette per questo specifico codice; ma ne trasmettono l'essenza generale - vedi la discussione nei commenti qui sotto per problemi specifici con questi esempi.

Potresti facilmente convertirlo in ricorsione. E ha una bella chiamata ricorsiva ottimizzata per la coda.

Pseudocodice:

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);
}

Mi piace molto la risposta di Jules , ma volevo anche sottolineare qualcosa a cui le persone spesso mancano del funzionale pigro programmazione, che è che tutto non deve essere "dentro al loop". Ad esempio:

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

Puoi vedere che ciascuna parte della tua logica può essere calcolata in una funzione separata e quindi composta insieme. Ciò consente di eseguire funzioni più piccole che in genere sono molto più semplici da risolvere. Per il tuo esempio di giocattolo, forse questo aggiunge più complessità di quanto rimuova, ma nel codice del mondo reale le funzioni divise sono spesso molto più semplici del tutto.

La maggior parte degli esempi di elaborazione degli elenchi che vedrai utilizzano funzioni come map , filter , sum ecc. che operano sull'elenco nel suo insieme. Ma nel tuo caso hai un'uscita anticipata condizionale - uno schema piuttosto insolito che non è supportato dalle solite operazioni di lista. Quindi devi abbassare un livello di astrazione e usare la ricorsione, che è anche più vicina a come appare l'esempio imperativo.

Questa è una traduzione piuttosto diretta (probabilmente non idiomatica) in 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))))))) 

Modifica: Jules sottolinea che reduce in Clojure fa supporta l'uscita anticipata. Usarlo è più elegante:

(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)))

In ogni caso, puoi fare qualsiasi cosa nelle lingue funzionali come puoi nelle lingue imperative, ma spesso devi cambiare un po 'la tua mentalità per trovare una soluzione elegante. Nella codifica imperativa si pensa di elaborare un elenco passo dopo passo, mentre nei linguaggi funzionali si cerca un'operazione da applicare a tutti gli elementi nell'elenco.

Come sottolineato da altre risposte, Clojure ha reduced per interrompere anticipatamente le riduzioni:

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

Questa è la soluzione migliore per la tua situazione particolare. Puoi anche ottenere molti chilometraggi combinando reduced con transduce , che ti consente di utilizzare trasduttori da map , filter ecc. Tuttavia è lontano da una risposta completa alla tua domanda generale.

Le continuazioni di fuga sono una versione generalizzata di break and return dichiarazioni. Sono implementati direttamente in alcuni Schemi ( call-with-escape-continuation ), Common Lisp ( block + return , catch + throw ) e persino C ( setjmp + longjmp ). Le continuazioni delimitate o non delimitate più generali che si trovano nello Schema standard o come monadi di continuazione in Haskell e Scala possono anche essere utilizzate come continuazione di escape.

Ad esempio, in Racket puoi usare let/ec in questo modo:

(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)))

Molti altri linguaggi hanno anche costrutti di continuazione di escape, come la gestione delle eccezioni. In Haskell puoi anche utilizzare una delle varie monadi di errore con foldM . Poiché si tratta principalmente di costrutti di gestione degli errori che utilizzano eccezioni o monade di errore per i ritorni anticipati, di solito è culturalmente inaccettabile e probabilmente piuttosto lento.

Puoi anche passare dalle funzioni di ordine superiore a quelle di coda.

Quando si utilizzano i loop, si immette automaticamente l'iterazione successiva quando si raggiunge la fine del corpo del loop. Puoi inserire la prossima iterazione in anticipo con continue o uscire dal ciclo con break (o return ). Quando si usano le chiamate tail (o il costrutto di loop di Clojure che riproduce la ricorsione in coda), è sempre necessario effettuare una chiamata esplicita per immettere l'iterazione successiva. Per interrompere il ciclo, non effettuare la chiamata ricorsiva, ma fornire direttamente il valore:

(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))))))

La parte complessa è il ciclo. Cominciamo da quello. Generalmente un ciclo viene convertito in stile funzionale esprimendo l'iterazione con una singola funzione. Un'iterazione è una trasformazione della variabile del ciclo.

Ecco un'implementazione funzionale di un loop generale:

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

Ci vuole (un valore iniziale della variabile loop, la funzione che esprime una singola iterazione [sulla variabile loop]) (una condizione per continuare il ciclo).

Il tuo esempio utilizza un ciclo su un array, che si rompe anche. Questa capacità nella tua lingua imperativa è cotta nel linguaggio stesso. Nella programmazione funzionale tale capacità viene solitamente implementata a livello di biblioteca. Ecco una possibile implementazione

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))

In esso:

Uso una coppia ((val, next_pos)) che contiene la variabile loop visibile all'esterno e la posizione nell'array, che questa funzione nasconde.

La funzione di iterazione è leggermente più complessa rispetto al ciclo generale, questa versione consente di utilizzare l'elemento corrente dell'array. [È in al curry modulo.]

Tali funzioni sono solitamente denominate "piega".

Ho inserito una "l" nel nome per indicare che l'accumulo degli elementi dell'array è fatto in modo associativo a sinistra; per imitare l'abitudine dei linguaggi di programmazione imperativi per iterare un array dall'indice basso a alto.

Ho inserito una "c" nel nome per indicare che questa versione di fold ha una condizione che controlla se e quando il ciclo deve essere interrotto anticipatamente.

Naturalmente è probabile che tali funzioni di utilità siano prontamente disponibili nella libreria di base fornita con il linguaggio di programmazione funzionale utilizzato. Li ho scritti qui per la dimostrazione.

Ora che abbiamo tutti gli strumenti che sono nella lingua nel caso imperativo, possiamo rivolgerci per implementare la funzionalità specifica del tuo esempio.

La variabile nel tuo ciclo è una coppia ('risposta', un valore booleano che codifica se continuare).

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)

Nota che ho usato una nuova "variabile" "new_answer". Questo perché nella programmazione funzionale non posso modificare il valore di una "variabile" già inizializzata. Non mi preoccupo delle prestazioni, il compilatore può riutilizzare la memoria di "risposta" per "new_answer" tramite l'analisi del tempo di vita, se ritiene che sia più efficiente.

Incorporando questo nella nostra funzione di loop sviluppata in precedenza:

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

"Array" qui è il nome del modulo che esporta la funzione foldlc è.

"pugno", "secondo" indicano le funzioni che restituiscono il primo, il secondo componente del suo parametro di coppia

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

In questo caso, lo stile "point-free" aumenta la leggibilità dell'implementazione di doSomeCalc:

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

(> > >) è la composizione della funzione: (>>>) : (a -> b) -> (b -> c) -> (a -> c)

È lo stesso di sopra, solo il parametro "arr" è escluso da entrambi i lati dell'equazione che definisce.

Un'ultima cosa: verificare il caso (array == null). Nei linguaggi di programmazione meglio progettati, ma anche in linguaggi mal progettati con una disciplina di base, uno piuttosto usa un tipo facoltativo per esprimere non- esistenza. Questo non ha molto a che fare con la programmazione funzionale, che alla fine riguarda la questione, quindi non la gestisco.