Mang theo thông tin về các tính toán trước

Question

Tôi mới làm quen với lập trình hàm, do đó một số vấn đề có vẻ khó giải quyết hơn bằng cách sử dụng phương pháp chức năng.

Giả sử tôi có danh sách các số, như 1 đến 10.000 và tôi muốn lấy các mục trong danh sách tổng cộng tối đa một số n (giả sử 100). Vì vậy, nó sẽ lấy các con số cho đến khi tổng của chúng lớn hơn 100.

Trong lập trình bắt buộc, nó là tầm thường để giải quyết vấn đề này, vì tôi có thể giữ một biến trong mỗi tương tác và dừng lại khi mục tiêu được đáp ứng.

Nhưng làm cách nào tôi có thể làm tương tự trong lập trình hàm? Vì hàm tổng hoạt động trên các danh sách đã hoàn thành, và tôi vẫn không có danh sách hoàn chỉnh, làm thế nào tôi có thể 'tiếp tục' tính toán?

Nếu tổng được lười biếng tính toán, tôi có thể viết một cái gì đó như thế:

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

PS: Mặc dù bất kỳ câu trả lời sẽ được đánh giá cao, tôi muốn một điều đó không có tính tổng mỗi lần, vì rõ ràng là phiên bản bắt buộc sẽ tối ưu hơn nhiều về tốc độ.

Chỉnh sửa:

Tôi biết rằng tôi có thể "chuyển đổi" phương pháp tiếp cận vòng lặp bắt buộc thành chức năng đệ quy chức năng. Tôi quan tâm nhiều hơn trong việc tìm kiếm xem một trong những chức năng thư viện hiện có có thể cung cấp một cách để tôi không viết một lần mỗi khi tôi cần thứ gì đó không.

Answer 1

Sử dụng 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:

thành phần Lấy không phải là rất khó khăn trong hai. Đây là cách bạn có thể làm điều đó:

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

Phần thứ hai của tuple là kết quả mong muốn của bạn.

Như hiển nhiên, trong trường hợp này, việc xây dựng một vectơ là lãng phí. Thay vào đó, chúng tôi chỉ có thể lưu trữ số cuối cùng từ luồng đã đóng góp vào tổng.

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

Cách tôi làm điều này là với đệ quy. Trên mỗi cuộc gọi, hãy thêm số tiếp theo. Trường hợp cơ sở của bạn là khi tổng lớn hơn 100, tại thời điểm đó bạn quay trở lại tất cả các con đường lên ngăn xếp. Bạn sẽ cần một hàm trợ giúp để thực hiện đệ quy thực sự, nhưng đó không phải là vấn đề lớn.

Answer 3

Điều này cũng không khó bằng phương pháp "chức năng".
Sử dụng đệ quy, thay vì duy trì trạng thái của bạn trong biến cục bộ mà bạn thay đổi, bạn giữ nó trong tham số và trả về giá trị.

Vì vậy, để trả lại bộ phận ban đầu dài nhất của một danh sách có tổng là tại hầu hết các N:

1. Nếu danh sách rỗng, bạn đã hoàn tất; trả về danh sách trống.
2. Nếu người đứng đầu danh sách lớn hơn N, bạn đã hoàn tất; trả về danh sách trống.
3. Nếu không, hãy H là người đứng đầu danh sách.
   Tất cả những gì chúng tôi cần bây giờ là phần đầu tiên của đuôi của danh sách có tổng số tối đa là N - H, sau đó chúng tôi có thể "chống" H vào danh sách đó và chúng tôi đã hoàn tất.
   Chúng tôi có thể tính toán đệ quy này bằng cách sử dụng thủ tục tương tự như chúng tôi đã sử dụng này đến nay, do đó, nó là một bước dễ dàng.

Một giải pháp giả đơn giản:

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

Tất cả các hoạt động chuỗi mà chỉ cần một đường chuyền qua chuỗi có thể được thực hiện bằng nếp gấp của chúng tôi giảm như nó đôi khi được gọi. tôi thấy mình sử dụng nếp gấp rất thường xuyên kể từ khi tôi trở thành sử dụng để lập trình chức năng

vì vậy đây lẻ một cách tiếp cận có thể Sử dụng một bộ sưu tập trống như giá trị ban đầu và gấp theo chiến lược này Với bộ sưu tập xử lý và kiểm tra giá trị mới nếu tổng của họ đủ thấp và nếu sau đó chi tiêu giá trị cho bộ sưu tập khác thì không có gì

giải pháp đó không hiệu quả nhưng tôi muốn nhấn mạnh bộ lọc bản đồ zip sau đây là cách để làm quen với lập trình hàm để sử dụng chúng càng nhiều càng tốt thay vì cấu trúc loping hoặc hàm đệ quy, mã của bạn sẽ khai báo nhiều hơn và hàm l