foldRight kuyruğunu tekrarlamak için devamlılık kullanmak mümkün mü?

Question

aşağıdaki blog article F # foldBack idame geçen stilini kullanarak kuyruk özyinelemeli yapılabilir gösterir.

Scala bu anlamına gelir:

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

yaparak kuyruk özyinelemeli yapılabilir:

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

Ne yazık ki, hala uzun listeler için bir yığın taşması olsun. döngü kuyruk özyinelemeli ve optimize edildi ama sanırım yığın birikimi sadece devam çağrılarına taşındı.

Neden bu F # ile bir sorun değildir? Ve Scala ile bunun etrafında çalışmak için herhangi bir yolu var mı?

Düzenleme: burada bazı kod yığınının derinliğini göstermektedir:

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)(_ + _) 

Bu baskılar:

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 

Answer 1

sorun devam fonksiyonu (racc => k(f(x, racc))) kendisidir. Bütün bu iş için çalışmak için en iyi duruma getirilmiş olmalı, ama değil.

Scala ilmeklere (yani fonksiyonu kendisini çağıran değil, başka bir fonksiyonu) dönüştürmek yalnızca için, rasgele kuyruk aramalar için tailcall optimizasyonlar yapamaz.

Answer 2

Neden bu F # ile bir sorun değildir?

F # optimize tüm kuyruk aramaları vardır.

Ve Scala ile bu geçici bir çözüm için herhangi bir yolu var mı?

Sen trambolin gibi diğer teknikler kullanılarak TCO'nuzu yapabilirsiniz ama ~ o çağırma kuralı değiştirir çünkü birlikte çalışma kaybeder ve o 10 × yavaş. Scala kullanmamamın üç sebebinden biri bu.

DÜZENLEME

Kişisel benchmark sonuçları Scala'nın trambolinler onlar bunları test son kez vardı daha çok daha hızlı olduğunu göstermektedir. Ayrıca, F # ve daha büyük listeler için eşdeğer kriterler eklemek ilginçtir (çünkü küçük listelerde CPS yapmada bir nokta yoktur!). Bir 1.67GHz N570 Intel Atom ile benim netbook 1.000 eleman listesinde 1.000X için

, alıyorum:

List.fold  0.022s 
List.rev+fold 0.116s 
List.foldBack 0.047s 
foldContTC 0.334s 

1x 1.000.000-eleman listesi için alıyorum:

List.fold  0.024s 
List.rev+fold 0.188s 
List.foldBack 0.054s 
foldContTC 0.570s 

Ayrıca, OCaml'ın kuyruksuz-özyinelemeli liste işlevlerini en iyi duruma getirilmiş kuyruk özyinelemeli olanlarla değiştirme bağlamında, bu konudaki eski tartışmalarla da ilgilenebilirsiniz.

Answer 3

Jon, n.m., cevaplarınız için teşekkürler. Yorumlarına dayanarak bir deneme yapıp trambolin kullanacağımı düşündüm. Biraz araştırma, Scala'nın TailCalls numaralı telefonunda trambolinlere kütüphane desteği verdiğini gösteriyor. Burada uğraşırsanız, biraz sonra geldi budur: Bu trambolin olmadan çözümü yanı sıra varsayılan foldLeft ve foldRight uygulamaları karşılaştırmasını görmek için ilgi

def foldContTC[T,U](list: List[T], acc: U)(f: (T, U) => U): U = { 
    import scala.util.control.TailCalls._ 
    @annotation.tailrec 
    def loop(l: List[T], k: (U) => TailRec[U]): TailRec[U] = { 
    l match { 
     case x :: xs => loop(xs, (racc => tailcall(k(f(x, racc))))) 
     case Nil => k(acc) 
    } 
    } 
    loop(list, u => done(u)).result 
} 

. İşte kriter kodu ve bazı sonuçlar ise:

val size = 1000 
val list = List.fill(size)(1) 
val warm = 10 
val n = 1000 
bench("foldContTC", warm, lots(n, foldContTC(list, 0)(_ + _))) 
bench("foldCont", warm, lots(n, foldCont(list, 0)(_ + _))) 
bench("foldRight", warm, lots(n, list.foldRight(0)(_ + _))) 
bench("foldLeft", warm, lots(n, list.foldLeft(0)(_ + _))) 
bench("foldLeft.reverse", warm, lots(n, list.reverse.foldLeft(0)(_ + _))) 

zamanlamaları şunlardır: Buna dayanarak

foldContTC: warming... 
Elapsed: 0.094 
foldCont: warming... 
Elapsed: 0.060 
foldRight: warming... 
Elapsed: 0.160 
foldLeft: warming... 
Elapsed: 0.076 
foldLeft.reverse: warming... 
Elapsed: 0.155 

, o tramplen aslında oldukça iyi bir performans elde edilir görünüyor. Boks/kutunun üstündeki cezanın nispeten o kadar da kötü olmadığından şüpheleniyorum.

Düzenleme: Jon'un yorumları tarafından önerildiği gibi, performansın daha büyük listelerle düştüğünü onaylayan 1M öğelerinin zamanlamaları aşağıdadır. Ayrıca ben kütüphane List.foldLeft uygulama yeri etkilenmez öğrendim, bu yüzden şu foldLeft2 ile zamanlanmış: ...

foldContTC: warming... 
Elapsed: 0.801 
foldLeft: warming... 
Elapsed: 0.156 
foldLeft2: warming... 
Elapsed: 0.054 
foldLeft.reverse: warming... 
Elapsed: 0.808 
foldLeft2.reverse: warming... 
Elapsed: 0.221 

Yani foldLeft2.reverse kazanır:

def foldLeft2[T,U](list: List[T], acc: U)(f: (T, U) => U): U = { 
    list match { 
    case x :: xs => foldLeft2(xs, f(x, acc))(f) 
    case Nil => acc 
    } 
} 

val size = 1000000 
val list = List.fill(size)(1) 
val warm = 10 
val n = 2 
bench("foldContTC", warm, lots(n, foldContTC(list, 0)(_ + _))) 
bench("foldLeft", warm, lots(n, list.foldLeft(0)(_ + _))) 
bench("foldLeft2", warm, lots(n, foldLeft2(list, 0)(_ + _))) 
bench("foldLeft.reverse", warm, lots(n, list.reverse.foldLeft(0)(_ + _))) 
bench("foldLeft2.reverse", warm, lots(n, foldLeft2(list.reverse, 0)(_ + _))) 

verimleri

Answer 4

Bu soruya geç kaldım, ama tam bir trambolin kullanmadan nasıl bir kuyruk özlü FoldRight yazabileceğinizi göstermek istedim;

object FoldRight { 

    def apply[A, B](list: Seq[A])(init: B)(f: (A, B) => B): B = { 
    @scala.annotation.tailrec 
    def step(current: Seq[A], conts: List[B => B]): B = current match { 
     case Seq(last) => conts.foldLeft(f(last, init)) { (acc, next) => next(acc) } 
     case Seq(x, xs @ _*) => step(xs, { acc: B => f(x, acc) } +: conts) 
     case Nil => init 
    } 
    step(list, Nil) 
    } 

} 

: devamlılık listesini biriktirme (yerine bir bellek taşması neden olan, yapıldığında bunları birbirlerine çağrı sahip olan) ve en sonunda bunların üzerine katlanır, bir tür gibi bir yığın tutmak, fakat yığın tarafından

Sonunda ortaya çıkan katlama, kuyruğunun kendiliğinden tekrarlanmasıdır. Bunu, performans açısından, kuyruk çağrı sürümünden biraz daha kötü performans gösterir.

[info] Benchmark   (length) Mode Cnt Score Error Units 
[info] FoldRight.conts   100 avgt 30 0.003 ± 0.001 ms/op 
[info] FoldRight.conts   10000 avgt 30 0.197 ± 0.004 ms/op 
[info] FoldRight.conts  1000000 avgt 30 77.292 ± 9.327 ms/op 
[info] FoldRight.standard  100 avgt 30 0.002 ± 0.001 ms/op 
[info] FoldRight.standard  10000 avgt 30 0.154 ± 0.036 ms/op 
[info] FoldRight.standard 1000000 avgt 30 18.796 ± 0.551 ms/op 
[info] FoldRight.tailCalls  100 avgt 30 0.002 ± 0.001 ms/op 
[info] FoldRight.tailCalls  10000 avgt 30 0.176 ± 0.004 ms/op 
[info] FoldRight.tailCalls 1000000 avgt 30 33.525 ± 1.041 ms/op