functional-programming - Okasaki's Purely Functional Data Structure のストリームの章

Question

ストリームの紹介の章で、岡崎氏はdropオンストリームの 2 つの実装を提供しています。

彼は、2 番目の方が効率的であると明言していますが (両方とも同じセマンティクスを持っています)、一方が他方よりも効率的である理由がわかりません。どんな洞察も大歓迎です。

Answer 1

推測する必要がある場合、これは、2 番目のバージョンが最初のバージョンほど遅延を利用していないという事実によるものであると言えますが、コンテキストに関係なく、少しでも強制すると結果、計算全体を強制します。たとえば、私がやりたかったとしましょう：

val x = hd ($drop(10, l))

最初のバージョンでは、最終的にコンス セルになる前に、10 回の反復すべてを実行する必要があります (ストリームに 10 個以上の要素があると仮定します)。これは、2 番目のバージョンでも実行される計算量と同じですが、各反復でサンクを作成して強制するオーバーヘッドに対処する必要はありません。

GHC のような特定のコンパイラは、厳密性分析と呼ばれるものを実際に実行します。この分析では、特定の用語が強制されるかどうかを判断しようとします。そうであれば、サンクを作成して強制する必要はありません。詳細については、ここで見つけることができます

take一方、

val x = hd ($take(10, l))

完全に遅延したバージョンでは、take停止できるまで の最初の反復のみを評価する必要がありますが、2 番目のバージョンのアナログは 10 回の反復すべてを評価します。この例では、遅延によっていくらか節約できます。