Come interrompere una funzione di riduzione dall'elaborare l'elenco una volta raggiunto l'accumulo desiderato?

Question

Nel mondo procedurale, se devo trovare il primo elemento di un elenco che soddisfa un test, vorrei semplicemente utilizzare break o return.

In Clojure, quando sto elaborando un elenco utilizzando reduce per trovare il primo valore, non sarà inefficiente se continuo ed elaboro l'intero elenco?

Ad esempio: convalida di un elenco di dizionari per errori; ogni dizionario ha una chiave chiamata count. Ora la somma totale di questi campi di conteggio nell'elenco non deve superare un determinato valore. Come trovo il primo elemento nell'elenco in cui la somma supera il limite?

Idealmente, vorrei usare reduce e mantenere un totale parziale; non appena il totale supera il limite, vorrei fermarmi qui (che non riesco a capire come fare).

Inoltre, il valore di ritorno della riduzione sarà la somma fino ad ora ogni volta ma avrei bisogno di restituire l'indice alla fine di tutto.

Answer 1

È possibile utilizzare la funzione reduced di interrompere una riduzione:

(reduce (fn [sum x] 
      (if (> sum 10) 
      (reduced 10) 
      (+ sum x))) 
     0 
     [1 2 3 4 5 6 7 8 9 10]) 

Answer 2

sarei tentato di utilizzare reductions piuttosto che reduce per trovare il punto di rottura. Questo è molto più lento di @Jonas's solution, ma ci permette di esercitare alcune delle librerie di sequenze.

Dato, ad esempio

(def data [{:count 19} 
      {:count 93} 
      {:count 89} 
      {:count 91} 
      {:count 55} 
      {:count 22} 
      {:count 22} 
      {:count 22} 
      {:count 40} 
      {:count 89}]) 

poi

(reductions + (map :count data)) 
; (19 112 201 292 347 369 391 413 453 542) 

... restituisce la sequenza di valori accumulati :count.

Supponiamo che il limite sia 300. Quindi

(let [acceptable (take-while 
        (partial >= 300) 
        (reductions + (map :count data)))] 
    acceptable) 
; (19 112 201 292) 

... restituisce la sequenza secondaria iniziale che soddisfa il criterio limite. Questo ci dice due cose che vogliamo sapere:

• Il suo elemento è il last accumulata :count.
• La sua lunghezza - restituita, in modo confuso, dalla funzione count - è la posizione, conteggiata da 0, del primo elemento rifiutato.

È possibile utilizzare la lunghezza, per esempio, per dividere la sequenza originale in parti accettate e quelle respinte:

(let [acceptable (take-while ...)] 
    (split-at (count acceptable) data)) 
; [({:count 19} {:count 93} {:count 89} {:count 91}) 
; ({:count 55} {:count 22} {:count 22} {:count 22} {:count 40} {:count 89})] 

Se sappiamo che la sequenza originale è un vettore, possiamo usare subvec per tirare le sue parti molto più veloci.

(let [acceptable (take-while ...) 
     point (count acceptable)] 
    [(subvec data 0 point) (subvec data point)]) 
; [[{:count 19} {:count 93} {:count 89} {:count 91}] 
; [{:count 55} {:count 22} {:count 22} {:count 22} {:count 40} {:count 89}]]