foldRight効率？

Question

私はfoldLeftがほとんどの操作においてはるかに効率的だと聞きましたが、Scala School（Twitterから）は次の例を示しました。誰かがその効率を分析できますか？foldLeftを使用して同じ操作を達成する必要がありますか？

val numbers = List(1,2,3,4,5,...10) 
def ourMap(numbers: List[Int], fn: Int => Int): List[Int] = { 
    numbers.foldRight(List[Int]()) { (x: Int, xs: List[Int]) => 
    fn(x) :: xs 
    } 
} 

scala> ourMap(numbers, timesTwo(_)) 
res0: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20) 

Answer 1

ドキュメントからわかるように、ListのfoldRightとfoldLeftメソッドはLinearSeqOptimizedで定義されています。だから、ソースを見てみましょう：

override /*TraversableLike*/ 
def foldLeft[B](z: B)(f: (B, A) => B): B = { 
    var acc = z 
    var these = this 
    while (!these.isEmpty) { 
    acc = f(acc, these.head) 
    these = these.tail 
    } 
    acc 
} 

override /*IterableLike*/ 
def foldRight[B](z: B)(f: (A, B) => B): B = 
    if (this.isEmpty) z 
    else f(head, tail.foldRight(z)(f)) 

だからfoldLeftは、whileループを使用し、foldRightは、単純な再帰的な方法を使用しています。特に、テール再帰的ではありません。したがって、foldRightは、新しいスタックフレームを作成するオーバーヘッドがあり、長いリストで試してみるとスタックがオーバーフローする傾向があります（たとえば((1 to 10000).toList :\ 0)(_+_)を試してみてください）。RangeのfoldRightが動作するので、toListなしでうまく動作します。左折を逆にする）。

なぜ、いつもfoldLeftを使用しないのですか？リンクされたリストは逆の順序で構築する必要があるため、リンクされたリストの場合、右折はおそらくもっと自然な関数です。上記の方法でfoldLeftを使用できますが、最後に出力をreverseにする必要があります。 （複雑さはO（N乗）であるとして、左倍にリストに追加しないでください。）

速く実際にされているとおり、foldRightまたはfoldLeft + reverseは、私は簡単なテストを実行し、foldRightですリストの場合は10〜40％速くなります。これは、ListのfoldRightがそのまま実装されている理由でなければなりません。

Answer 2

foldRightはリストを逆にしてfoldLeftを適用します。