Noś informacje o poprzednich obliczeniach

Question

Jestem nowicjuszem w zakresie programowania funkcjonalnego, więc niektóre problemy wydają się trudniejsze do rozwiązania za pomocą podejścia funkcjonalnego.

Załóżmy, że mam listę liczb, na przykład od 1 do 10 000, i chcę uzyskać pozycje listy, które sumują się do co najwyżej liczby n (powiedzmy 100). Tak więc otrzymywałby liczby, dopóki ich suma nie przekroczy 100.

W programowaniu imperatywnym, jest to dość trywialne, aby rozwiązać ten problem, ponieważ mogę zachować zmienną w każdej interakcji i zatrzymać się, gdy cel zostanie osiągnięty.

Ale jak mogę zrobić to samo w programowaniu funkcjonalnym? Ponieważ funkcja sumowania działa na zakończonych listach, a ja wciąż nie mam ukończonej listy, jak mogę "kontynuować" obliczenia?

Jeśli suma leniwie komputerowej, mogę napisać coś takiego:

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

PS: Chociaż każda odpowiedź będzie mile widziane, chciałbym taki, który nie obliczyć sumę za każdym razem, ponieważ oczywiście wersja imperatywna będzie znacznie bardziej optymalna pod względem prędkości.

Edit:

wiem, że mogę „przerobić” podejście pętli koniecznie funkcjonalnego funkcji rekurencyjnej. Jestem bardziej zainteresowany znalezieniem, czy jedna z istniejących funkcji bibliotecznych może zapewnić mi możliwość nie pisania jej za każdym razem, gdy czegoś potrzebuję.

Answer 1

Użyj 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:

Uzyskanie komponenty nie jest bardzo trudne, albo. Oto, jak możesz to zrobić:

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

Druga część krotki to pożądany rezultat.

Jak powinno być oczywiste, w tym przypadku budowanie wektora jest marnotrawstwem. Zamiast tego możemy zapisać ostatnią liczbę ze strumienia, który przyczynił się do sumy.

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

Sposób w jaki to zrobię jest z rekursją. Przy każdym połączeniu dodaj kolejny numer. Twój podstawowy przypadek ma miejsce wtedy, gdy suma jest większa niż 100, po czym następuje powrót do stosu. Będziesz potrzebował funkcji pomocnika, aby wykonać rzeczywistą rekursję, ale to nic wielkiego.

Answer 3

Nie jest to trudne przy użyciu metod "funkcjonalnych".
Korzystanie z rekursji zamiast utrzymywania stanu w zmiennej lokalnej, którą modyfikujesz, zachowujesz ją w parametrach i zwracanych wartościach.

Tak, aby powrócić najdłuższy początkową część listy, których suma wynosi co najwyżej N:

1. Jeżeli lista jest pusta, skończysz; zwróć pustą listę.
2. Jeśli nagłówek listy jest większy niż N, gotowe; zwróć pustą listę.
3. W przeciwnym razie, niech H będzie głową listy.
   Wszystko, czego potrzebujemy, to początkowa część ogona, której suma wynosi co najwyżej N - H, wtedy możemy "przeciw" H na tę listę, i jesteśmy skończeni.
   Możemy to obliczać rekurencyjnie, używając tej samej procedury, z której korzystaliśmy tak daleko, więc jest to łatwy krok.

Prostym rozwiązaniem pseudokod:

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

Wszystkie operacje sekwencyjne, które wymagają tylko jedno podanie za pośrednictwem sekwencji mogą być realizowane z wykorzystaniem fałdy naszych zmniejszyć jak to jest czasami nazywane. łapię się za pomocą fałdy bardzo często, ponieważ stałem stosowany do programowania funkcyjnego

więc tutaj dziwne jedno możliwe podejście Zastosowanie pusty zbiór jako wartości początkowej i złożyć zgodnie z tą strategią Given przetworzonego i nowego czek wartości, jeżeli ich suma jest wystarczająco niska, a jeśli następnie wydasz wartość do kolekcji, to nie rób nic, to nie musisz nic robić, aby rozwiązać problem niezbyt wydajnie, ale chcę podkreślić, że następujący po nim zszywacz filtra składanego na mapę itp. to sposób na przyzwyczajenie się do programowania funkcjonalnego. aby używać ich jak najwięcej, zamiast budowania pętli lub funkcji rekurencyjnych, twój kod będzie bardziej deklaratywny i funkcjonalny l