HaskellWiki/Fold を読んでいたら、foldr と foldl が簡単に再帰的定義で定義できるのが分かった。
そこで myfold.hs というファイルに次のように myfoldr と myfoldl を定義してみた。 ファイル名 : myfold.hs myfoldr f z [] = z myfoldr f z (x:xs) = f x (myfoldr f z xs) myfoldl f z [] = z myfoldl f z (x:xs) = myfoldl f (f z x) xs これを ghci に load して実行してみたら、驚いたことに myfoldr がちゃんと foldr として動いた。 Prelude> :e myfold.hs Prelude> :l myfold.hs [1 of 1] Compiling Main Ok, modules loaded: Main. *Main> myfoldr (+) 0 [1..5] 15 *Main> myfoldl (*) 1 [1..5] 120 foldr の中身が再帰的定義として分かっていれば、動作の解析も簡単だ。myfoldr (+) 0 [1..5] を定義に従って展開すると次のようになる。 myfoldr (+) 0 [1,2,3,4,5] = 1 + (myfoldr (+) 0 [2,3,4]) = 1 + (2 + (myfoldr (+) 0 [3,4])) = 1 + (2 + (3 + (myfoldr (+) 0 [4,5]))) = 1 + (2 + (3 + (4 + (myfoldr (+) 0 [5])))) = 1 + (2 + (3 + (4 + (5 + (myfoldr (+) 0 []))))) = 1 + (2 + (3 + (4 + (5 + 0)))) = 15 この展開式を見ると foldr の値が計算を途中で中断してもそれまでの段階の値を得る事ができるのがわかる。したがって、foldr は無限リストに対しても適用できることが理解できる。これとは逆に foldl の場合は全ての式の展開が行われなければ部分的な値さえ得る事ができない。 foldr のような基本的な関数についても内部的な構造をユーザが知ることができるのが Haskell の良いところだ。
by tnomura9
| 2011-08-24 23:39
| Haskell
|
Comments(0)
|
カテゴリ
新型コロナウイルス 主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude Ocaml ボーカロイド 圏論 jQuery デモ HTML Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker ed と sed HTML Raspberry Pi C 言語 命題論理 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||