9
Sau đây blog article cho thấy làm thế nào trong F # foldBack có thể được thực hiện đệ quy đuôi bằng cách sử dụng tiếp tục đi qua phong cách.Có thể sử dụng phần tiếp tục để làm cho phần đuôi gập đệ quy không?
Trong Scala này sẽ có nghĩa là:
def foldBack[T,U](l: List[T], acc: U)(f: (T, U) => U): U = {
l match {
case x :: xs => f(x, foldBack(xs, acc)(f))
case Nil => acc
}
}
thể được thực hiện đệ quy đuôi bằng cách làm này:
def foldCont[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
@annotation.tailrec
def loop(l: List[T], k: (U) => U): U = {
l match {
case x :: xs => loop(xs, (racc => k(f(x, racc))))
case Nil => k(acc)
}
}
loop(list, u => u)
}
Thật không may, tôi vẫn nhận được một lỗi tràn stack cho danh sách dài. vòng lặp là đuôi đệ quy và tối ưu hóa nhưng tôi đoán sự tích lũy chồng chỉ là di chuyển vào các cuộc gọi tiếp tục.
Tại sao đây không phải là vấn đề với F #? Và có cách nào để giải quyết vấn đề này với Scala không?
Sửa: ở đây một số mã cho thấy chiều sâu của stack:
def showDepth(s: Any) {
println(s.toString + ": " + (new Exception).getStackTrace.size)
}
def foldCont[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
@annotation.tailrec
def loop(l: List[T], k: (U) => U): U = {
showDepth("loop")
l match {
case x :: xs => loop(xs, (racc => { showDepth("k"); k(f(x, racc)) }))
case Nil => k(acc)
}
}
loop(list, u => u)
}
foldCont(List.fill(10)(1), 0)(_ + _)
in này:
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
k: 51
k: 52
k: 53
k: 54
k: 55
k: 56
k: 57
k: 58
k: 59
k: 60
res2: Int = 10
Điều đó không có ý nghĩa. Bạn có một trường hợp thử nghiệm đơn giản? –
@ DanielC.Sobral, xem mã tôi đã thêm và nó in. – huynhjl