人気ブログランキング | 話題のタグを見る

RWH の読み方(39) 第4章

Real World Haskell 第4章 Functional Programming

Left Folds, Laziness, and Space Leaks

このサブセクションでは Data.List モジュールの foldl' が解説されている。

How to Think About Loops セクションを通じて畳込み関数については foldl を中心に述べられている。それは、foldl が末尾再帰関数と同等と考えてよいので手続き型の言語のループを Haskell の再帰関数に翻訳するときに便利だったからだ。

しかし、foldl は実用的なプログラムでは余り使われない。それは、遅延評価の実装の関係で、foldl は計算の手順を保存した thunk の形でメモリに保存されるからだ。thunk の形で保存にされていた式は、その評価が必要となった時に、GHC によってスタックに展開されて計算される。

したがって、foldl を遅延評価の状態で使用するときは、thunk として保存されるための多量のメモリと、評価の際のスタックの消費が必要となり、メモリ効率と速度の点でかなり効率の悪い実装になってしまう。

foldl' は foldl の計算を遅延評価ではなく正格で行うため、thunk が発生せず、メモリ効率と速度の点で有利だ。

それは、次の foldl と foldl' の計算にかかる時間を見ると良く分かる。

Prelude> foldl (+) 0 [1..100000]
5000050000
Prelude> :m +Data.List
Prelude Data.List> foldl' (+) 0 [1..100000]
5000050000

このため、理論的には foldl でプログラムを設計するが、実用的には foldl' を使うことになる。

Further Reading

このサブセクションでは、Graham Hutton の論文 "A tutorial on the universality and expressiveness of fold" が紹介されている。

長い道のりだったが、これで How to Think About Loops セクションは終わりだ。Haskell の第1の関門がループ(Haskell ではあくまで再帰関数であってループではないが)の記述法だ。このサブセクションで述べられたことを活用すれば、ループの記述であまり迷うことはないだろう。
by tnomura9 | 2012-04-29 02:44 | Haskell | Comments(0)
<< RWH の読み方(40) 第4章 どうして「なぜ?」が必要か。 >>