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)
|
カテゴリ
新型コロナウイルス 主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude Ocaml ボーカロイド 圏論 jQuery デモ HTML Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker ed と sed HTML Raspberry Pi C 言語 命題論理 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||