Informazioni sui calcoli precedenti

Question

Sono nuovo alla programmazione funzionale, quindi alcuni problemi sembrano più difficili da risolvere utilizzando un approccio funzionale.

Diciamo che ho una lista di numeri, come 1 a 10.000, e voglio ottenere gli elementi della lista che riassume al massimo un numero n (diciamo 100). Quindi, otterrebbe i numeri fino a quando la loro somma è maggiore di 100.

Nella programmazione imperativa, è banale risolvere questo problema, perché posso mantenere una variabile in ogni interazione e fermarsi una volta raggiunto l'obiettivo.

Ma come posso fare lo stesso nella programmazione funzionale? Dato che la funzione somma funziona su liste completate, e io ancora non ho la lista completa, come posso 'portare avanti' il calcolo?

Se somma è stata calcolata pigramente, potrei scrivere qualcosa di simile:

  (1 to 10000).sum.takeWhile(_ < 100) 

PS: Anche se una risposta sarà apprezzato, vorrei uno che non calcola la somma di volta in volta, dal momento che ovviamente la versione imperativa sarà molto più ottimale per quanto riguarda la velocità.

Edit:

So che posso "convertire" l'approccio ad anello indispensabile per una funzione ricorsiva funzionale. Sono più interessato a scoprire se una delle funzioni di libreria esistenti può fornire un modo per non scriverne una ogni volta che ho bisogno di qualcosa.

Answer 1

Utilizzare Stream.

scala> val ss = Stream.from(1).take(10000) 
ss: scala.collection.immutable.Stream[Int] = Stream(1, ?) 

scala> ss.scanLeft(0)(_ + _) 
res60: scala.collection.immutable.Stream[Int] = Stream(0, ?) 

scala> res60.takeWhile(_ < 100).last 
res61: Int = 91 

EDIT:

componenti Ottenere non è molto difficile sia. Ecco come si può fare:

scala> ss.scanLeft((0, Vector.empty[Int])) { case ((sum, compo), cur) => (sum + cur, compo :+ cur) } 
res62: scala.collection.immutable.Stream[(Int, scala.collection.immutable.Vector[Int])] = Stream((0,Vector()), ?) 

scala> res62.takeWhile(_._1 < 100).last 
res63: (Int, scala.collection.immutable.Vector[Int]) = (91,Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)) 

La seconda parte della tupla è il risultato desiderato.

Come dovrebbe essere ovvio, in questo caso, la costruzione di un vettore è uno spreco. Invece possiamo solo memorizzare l'ultimo numero dal flusso che ha contribuito alla somma.

scala> ss.scanLeft(0)(_ + _).zipWithIndex 
res64: scala.collection.immutable.Stream[(Int, Int)] = Stream((0,0), ?) 

scala> res64.takeWhile(_._1 < 100).last._2 
res65: Int = 13 

Answer 2

Il modo in cui lo farei è con la ricorsione. Ad ogni chiamata, aggiungi il numero successivo. Il tuo caso base è quando la somma è maggiore di 100, a quel punto si ritorna in cima allo stack. Avrai bisogno di una funzione di supporto per eseguire la ricorsione vera e propria, ma non è un grosso problema.

Answer 3

Questo non è difficile con i metodi "funzionali" o.
Utilizzando la ricorsione, anziché mantenere il proprio stato in una variabile locale che si modifica, lo si mantiene nei parametri e si restituiscono i valori.

Quindi, per tornare alla parte iniziale più lunga di una lista la cui somma è al massimo N:

1. Se l'elenco è vuoto, il gioco è fatto; restituire la lista vuota.
2. Se il capo dell'elenco è maggiore di N, il gioco è fatto; restituire la lista vuota.
3. Altrimenti, sia H il capo della lista.
   Tutti abbiamo bisogno ora è la parte iniziale del coda della lista la cui somma è al massimo N - H, allora possiamo "contro" H su quella lista, e abbiamo finito.
   Possiamo calcolarlo ricorsivamente usando la stessa procedura che abbiamo usato fino ad ora, quindi è un passo facile.

Una soluzione semplice pseudocodice:

sum_to (n, ls) = if isEmpty ls or n < (head ls) 
       then Nil 
       else (head ls) :: sum_to (n - head ls, tail ls) 

sum_to(100, some_list) 

Answer 4

Tutte le operazioni di sequenza che richiedono solo passaggio attraverso la sequenza possono essere implementate utilizzando pieghe nostro riducono come è talvolta chiamato. mi trovo con pieghe molto spesso da quando sono diventato utilizzato per la programmazione funzionale

ecco dispari una possibile approccio utilizzare una raccolta vuota come valore iniziale e piegare in base a questa strategia di Data la raccolta elaborato e il nuovo controllo valore se la loro somma è abbastanza basso e se poi passare il valore alla collezione altro fare nulla

che la soluzione non è molto efficiente, ma voglio sottolineare il seguente carta filtro piega zip ecc sono il modo per abituarsi a funzionale prova di programmazione per usarli il più possibile invece di costrutti loping o funzioni ricorsive il tuo codice sarà più dichiarativo e funzionale l