Luồng nối tiếp đệ quy của các cặp số nguyên (Scala)?

Question

Tôi rất mới với Scala, vì vậy hãy tha thứ cho sự thiếu hiểu biết của tôi! Tôi đang cố gắng để lặp đi lặp lại của cặp số nguyên được giới hạn bởi một tối đa. Ví dụ, nếu mức tối đa là 5, sau đó lặp nên quay lại:

(0, 0), (0, 1), ..., (0, 5), (1, 0), ..., (5, 5) 

tôi đã chọn để thử và đuôi-đệ quy quay trở lại này như một Stream:

@tailrec 
    def _pairs(i: Int, j: Int, maximum: Int): Stream[(Int, Int)] = { 
     if (i == maximum && j == maximum) Stream.empty 
     else if (j == maximum) (i, j) #:: _pairs(i + 1, 0, maximum) 
     else (i, j) #:: _pairs(i, j + 1, maximum) 
    } 

Nếu không có chú thích tailrec sự mã hoạt động:

scala> _pairs(0, 0, 5).take(11) 
res16: scala.collection.immutable.Stream[(Int, Int)] = Stream((0,0), ?) 

scala> _pairs(0, 0, 5).take(11).toList 
res17: List[(Int, Int)] = List((0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (1,0), (1,1), (1,2), (1,3), (1,4)) 

Nhưng điều này không đủ tốt cho tôi. Trình biên dịch được một cách chính xác chỉ ra rằng dòng cuối cùng của _pairs không trả _pairs:

could not optimize @tailrec annotated method _pairs: it contains a recursive call not in tail position 
    else (i, j) #:: _pairs(i, j + 1, maximum) 
       ^

Vì vậy, tôi có một vài câu hỏi:

• trực tiếp giải quyết việc thực hiện ở trên, như thế nào trở lại một đuôi-đệ quy Luồng [(Int, Int)]?
• thực hiện một bước trở lại, cách hiệu quả nhất về bộ nhớ để lặp qua chuỗi các số nguyên bị chặn là gì? Tôi không muốn lặp qua Phạm vi vì Range extends IndexedSeq và tôi không muốn chuỗi đó tồn tại hoàn toàn trong bộ nhớ. Hoặc là tôi sai? Nếu tôi lặp qua Range.view thì tôi có tránh nó vào bộ nhớ không? (!)

Trong Python, tất cả tôi muốn là:

In [6]: def _pairs(maximum): 
    ...:  for i in xrange(maximum+1): 
    ...:   for j in xrange(maximum+1): 
    ...:    yield (i, j) 
    ...:    

In [7]: p = _pairs(5) 

In [8]: [p.next() for i in xrange(11)] 
Out[8]: 
[(0, 0), 
(0, 1), 
(0, 2), 
(0, 3), 
(0, 4), 
(0, 5), 
(1, 0), 
(1, 1), 
(1, 2), 
(1, 3), 
(1, 4)] 

Nhờ sự giúp đỡ của bạn! Nếu bạn nghĩ rằng tôi cần phải đọc tài liệu tham khảo/tài liệu API/bất cứ điều gì khác xin vui lòng cho tôi biết, bởi vì tôi rất muốn học.

Answer 1

Đây không phải là đuôi-đệ quy

Giả sử bạn đã thực hiện một danh sách thay vì một dòng: (hãy để tôi sử dụng một chức năng đơn giản để làm cho quan điểm của tôi)

def foo(n: Int): List[Int] = 
    if (n == 0) 
    0 :: Nil 
    else 
    n :: foo(n - 1) 

Trong trường hợp tổng quát trong đệ quy này, sau khi foo(n - 1) trả về hàm phải làm điều gì đó với danh sách mà nó trả về - nó phải nối một mục khác vào đầu danh sách. Vì vậy, các chức năng không thể được đuôi đệ quy, bởi vì một cái gì đó đã được thực hiện vào danh sách sau khi đệ quy.

Nếu không có đệ quy đuôi, đối với một số giá trị lớn là n, bạn sẽ hết dung lượng ngăn xếp.

Danh sách thông thường giải pháp

Giải pháp thông thường sẽ phải vượt qua một ListBuffer như một tham số thứ hai, và điền vào đó.

def foo(n: Int) = { 
    def fooInternal(n: Int, list: ListBuffer[Int]) = { 
    if (n == 0) 
     list.toList 
    else { 
     list += n 
     fooInternal(n - 1, list) 
    } 
    } 
    fooInternal(n, new ListBuffer[Int]()) 
} 

gì bạn đang làm được gọi là "tail recursion modulo cons", và đây là một tối ưu hóa thực hiện tự động bởi trình biên dịch LISP Prolog khi họ nhìn thấy modulo đệ quy đuôi Nhược điểm mô hình, vì nó quá phổ biến. Trình biên dịch của Scala không tự động tối ưu hóa điều này.

Streams không cần đệ quy đuôi

Streams không cần đệ quy đuôi để tránh chạy ra khỏi ngăn xếp không gian - điều này là bởi vì họ sử dụng một thủ thuật thông minh để tránh thực hiện các cuộc gọi đệ quy để foo tại điểm xuất hiện trong mã. Các cuộc gọi chức năng được bọc trong một thunk, và chỉ được gọi là tại điểm mà bạn thực sự cố gắng để có được giá trị từ dòng. Chỉ có một cuộc gọi đến foo hoạt động tại một thời điểm - nó không bao giờ đệ quy.

Tôi đã viết câu trả lời trước giải thích how the #:: operator works tại đây trên Stackoverflow. Đây là những gì sẽ xảy ra khi bạn gọi hàm đệ quy sau đây. (Đó là đệ quy theo nghĩa toán học, nhưng nó không thực hiện cuộc gọi chức năng từ bên trong một hàm gọi theo cách bạn thường mong đợi.)

def foo(n: Int): Stream[Int] = 
    if (n == 0) 
    0 #:: Nil 
    else 
    n #:: foo(n - 1) 

Bạn gọi foo(10), nó sẽ trả về một dòng với một yếu tố tính đã và đuôi là một đoạn sẽ gọi foo(9) vào lần tiếp theo bạn cần một phần tử từ luồng. foo(9) không được gọi ngay bây giờ - thay vào đó cuộc gọi được liên kết với một số lazy val bên trong luồng và foo(10) trả về ngay lập tức. Khi bạn cuối cùng cần giá trị thứ hai trong luồng, foo(9) được gọi và nó tính toán một phần tử và đặt đuôi của luồng hte thành một đoạn sẽ gọi là foo(8). foo(9) trả về ngay lập tức mà không cần gọi số foo(8). Và vân vân ...

này cho phép bạn tạo ra các dòng vô hạn mà không cần chạy ra khỏi bộ nhớ, ví dụ:

def countUp(start: Int): Stream[Int] = start #::countUp(start + 1) 

(Hãy cẩn thận những gì hoạt động bạn gọi vào hoạt động này Nếu bạn cố gắng làm một. forEach hoặc một map, bạn sẽ lấp đầy cả đống bạn, nhưng sử dụng take là một cách tốt để làm việc với một tiền tố độc đoán của con suối.)

một giải pháp đơn giản hoàn toàn

Thay vì đối phó với tái cursion và suối, tại sao không chỉ sử dụng vòng lặp for của Scala?

def pairs(maximum:Int) = 
    for (i <- 0 to maximum; 
     j <- 0 to maximum) 
    yield (i, j) 

Điều này thực hiện toàn bộ bộ sưu tập trong bộ nhớ và trả lại IndexedSeq[(Int, Int)].

Nếu bạn cần một Dòng cụ thể, bạn có thể chuyển đổi phạm vi đầu tiên thành Stream.

def pairs(maximum:Int) = 
    for (i <- 0 to maximum toStream; 
     j <- 0 to maximum) 
    yield (i, j) 

Điều này sẽ trả lại Stream[(Int, Int)]. Khi bạn truy cập vào một điểm nhất định trong chuỗi, nó sẽ được vật hoá thành bộ nhớ, và nó sẽ dính xung quanh miễn là bạn vẫn có một tham chiếu đến bất kỳ điểm nào trong luồng trước phần tử đó.

Bạn có thể sử dụng bộ nhớ tốt hơn nữa bằng cách chuyển đổi cả hai phạm vi thành chế độ xem.

def pairs(maximum:Int) = 
    for (i <- 0 to maximum view; 
     j <- 0 to maximum view) 
    yield (i, j) 

Điều đó trả về mỗi phần tử mỗi lần bạn cần và không lưu trữ kết quả precomputed.

Bạn cũng có thể nhận được một iterator (mà bạn chỉ có thể đi qua một lần) theo cùng một cách

def pairs(maximum:Int) = 
    for (i <- 0 to maximum iterator; 
     j <- 0 to maximum iterator) 
    yield (i, j) 

Đó trả Iterator[(Int, Int)].

Answer 2

Có thể một Iterator phù hợp hơn với bạn?

class PairIterator (max: Int) extends Iterator [(Int, Int)] { 
    var count = -1 
    def hasNext = count <= max * max 
    def next() = { count += 1; (count/max, count % max) } 
} 

val pi = new PairIterator (5) 
pi.take (7).toList