List foldRight總是使用foldLeft？

我剛纔看了List.scala的foldRight()的實現。List foldRight總是使用foldLeft？

override def reverse: List[A] = { 
    var result: List[A] = Nil 
    var these = this 
    while (!these.isEmpty) { 
     result = these.head :: result 
     these = these.tail 
    } 
    result 
    } 

    override def foldRight[B](z: B)(op: (A, B) => B): B = 
    reverse.foldLeft(z)((right, left) => op(left, right))

據我瞭解，呼籲在List結果foldRight呼籲theList.reverse.foldLeft(...)。

是List.foldRight實現與foldLeft爲了利用單個堆棧幀，而不是使用多個堆棧幀與foldLeft？

來源

2013-10-23 Kevin Meredith

從2.10開始，實現似乎已經發生了變化！ 'foldRight'曾經是簡單的遞歸，比倒退和摺疊式快10％ - 40％。 http://stackoverflow.com/questions/11004715/foldright-efficiency和2.10.0來源：https：//github.com/scala/scala/blob/v2.10.0/src/library/scala/collection/immutable/List .scala＃L1 –

爲什麼它會改變，Luigi？ –

堆棧溢出錯誤。我認爲馬丁一直在追求審美和性能方面的原因。 –

foldLeft是尾遞歸的，reverse根本不是遞歸的：這個實現確保了內存的持續使用。 foldRight，如果沒有按照foldLeft執行，則不是尾遞歸的，這使得它對大量數據不安全。

注意：可能有辦法使尾部遞歸成爲foldRight，但是我所能想到的所有這些都需要在列表的末尾添加事物，這意味着要遍歷整個列表。如果你仍然要這樣做，最好使用foldLeft並將結果逆轉，它會在整個列表中涉及更少的完整迭代。

來源

2013-10-23 17:38:03

儘管當前版本是尾遞歸的，但是反轉列表的成本將會疊加...因此，如果您連續多次執行此操作，請使用'foldLeft'並在最後反轉列表...或者甚至更好，嘗試一個最適合你的需求的集合，比如'Vector'。 –

[修復以前刪除的評論]只是爲了補充Nicolas Rinaudo的答案，'while while循環快！功能+不變的成語往往會更好地擴展。勢在必行+可變的風格往往會有更好的原始表現。所以反向需要線性時間，但實際上很快。 'foldRight'被增強爲用戶反轉+ foldRight，之前它不是尾遞歸（參見v2.0 [List.scala]（https://github.com/scala/scala/blob/78c4deeb632f850357a0c938f33d0f556756f64c/src/library/scala/） List.scala））。無論如何，線性時間是線性時間，所以，只要你可以，按照上面的建議。 –

作爲一個有趣的筆記，Scalaz按照'foldRight'實現了'Foldable＃foldLeftM'。 – Hugh

List foldRight總是使用foldLeft？

回答

相關問題