5

List of String で右折畳み (:\) を実行したため、スタック オーバーフローが発生しました。しかし、左折りたたみ (/:) を使用するように変更すると、問題なく動作しました。なんで？

4

2 に答える 2

10

ソースが公開されているので、 LinearSeqOptimized.scalaで実際に実装を見ることができます:

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ループ戦略は非常に効率的ですが、再帰では、リスト内のすべての要素に対してフレームをスタックにプッシュする必要があります (最後までトラバースするため)。これが、正常に動作するのにスタック オーバーフローを引き起こす理由foldLeftですfoldRight。

于 2012-12-28T20:52:07.767 に答える
1

Foldは、再帰的なデータ構造をトラバースし、通常は単一の値（参照）になる、一般的に使用される関数の一般的なセットです。シーケンスとリストでは、FoldLeft（一般的な意味で）は末尾再帰であるため、最適化できます。FoldRightは末尾再帰ではないため、末尾呼び出しを最適化することはできません。ただし、無限級数に適用できるという利点があります。

Scalaライブラリ（@dhgの回答から海賊版）の実装foldLeftとそこからの実装は、この最適化/欠如を反映しています。whileループを使用して手動で末尾呼び出しを最適化しました。することはできません。foldRightfoldLeftfoldRight

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

Odersky、Spoon、VennersonfoldsによるProgramminginScala、Second Editionには、無限リストfoldLeftで実行できる可能性がある一方で、リストでの末尾再帰の方法を説明するセクションがあると思います。foldRight残念ながら、ページ番号などを提供するために、現時点では私はそれを持っていません。そうでなければ、これを証明することはそれほど難しくありません。

MiranLipovačaによるLearnYoua Haskell forGreatGoodのフォールドのセクションも参照してください。

再帰を扱っていたとき、リストを操作する再帰関数の多くでテーマに気づきました。通常、空のリストにはエッジケースがあります。x：xsパターンを導入してから、単一の要素とリストの残りの部分を含むアクションを実行します。これは非常に一般的なパターンであることが判明したため、カプセル化するためにいくつかの非常に便利な関数が導入されました。これらの関数はフォールドと呼ばれます。

于 2012-12-28T23:18:40.030 に答える