Haskell のリスト操作関数のうちとりわけ有用なのが、map、filter、fold(r/l) だ。このうち、map や filter は直感的にわかりやすいのですぐに使えるようになる。map はリストの要素それぞれに関数を作用させた結果のリストを作成するし、filter は述語の条件に合う要素だけのリストを作成する。
Hugs> map (^2) [1..10] [1,4,9,16,25,36,49,64,81,100] Hugs> filter even [1..10] [2,4,6,8,10] しかし、fold (畳み込み)については、直感的な理解が難しい。リストの総和や階乗を同じ関数で計算できる便利なものだが、どうしてそうなるのかをイメージできないからだ。 Hugs> foldr (+) 0 [1..10] 55 Hugs> foldr (*) 1 [1..10] 3628800 だが、foldr については、リストの (:) 演算子を引数の演算子で置き換えるというイメージで理解することができる。Haskell ではリストは [1, 2, 3, 4, 5] のように表記するが、これは (:) (cons 演算子)を使った、次のような定義のシンタックスシュガーだ。 1 : ( 2 : ( 3 : ( 4 : ( 5 : [] )))) foldr の動作は上の (:) 演算子を、foldr の引数で置き換え、[] (空リスト)を引数の初期条件(base case) で置き換えてやればいい。たとえば、foldr (+) 0 [1..5] は次のようになる。 foldr (+) 0 [1..5] == 1 + ( 2 + ( 3 + ( 4 + ( 5 + 0 )))) == 15 foldr の引数の演算子が (+) で初期条件が 1 の場合は、 foldr (*) 1 [1..5] == 1 * ( 2 * ( 3 * ( 4 * ( 5 * 1 )))) == 120 となる。これは、次のように再帰的な定義で記述された関数の動作と同じになる。 fact 0 = 1 fact n = n * fact (n-1) fact 5 == 5 * fact 4 == 5 * ( 4 * fact 3) == 5 * ( 4 * ( 3 * fact 2)) == 5 * ( 4 * ( 3 * ( 2 * fact 1))) == 5 * ( 4 * ( 3 * ( 2 * (1 * fact0)))) == 5 * ( 4 * ( 3 * ( 2 * (1 * 1)))) == 120 つまり、foldr は初期条件までを含んで、関数の再帰的定義を一行で表現したものと考えられる。そう考えると、リストの総和や階乗以外の foldr の使い方が見える。例えば max という関数は二つの引数をとり、大きい方を返すが、 Hugs> max 1 2 2 これを foldr の引数にしてやると、リストの中の最大値を見つけてくれる。 Hugs> foldr max 0 [25, 2, 49, 9] 49 この動作は次のように理解できる。 foldr max 0 [25, 2, 49, 9] == max 25 ( max 2 ( max 49 (max 9 0))) == max 25 ( max 2 ( max 49 9 )) == max 25 ( max 2 49 ) == max 25 49 == 49 また、foldr は次のように文字列にも適用できる。 Hugs> foldr (\x y -> x ++ "\n" ++ y) [] ["hello", "world"] "hello\nworld\n" foldr が初期値の指定を含めた再帰関数を定義している事が分かれば、コンパクトな記述をするための強力な道具になる。 今日の Haskell Hugs> takeWhile (<5) [1, 3, 2, 5, 3] [1,3,2] Hugs> dropWhile (<5) [1, 3, 2, 5, 3] [5,3] 後の方に条件に合致する要素があっても、最初に条件を満たさない要素があったところで処理が中断されるところが filter とは異なっている。
by tnomura9
| 2010-11-28 09:22
| Haskell
|
Comments(0)
|
カテゴリ
新型コロナウイルス 主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude Ocaml ボーカロイド 圏論 jQuery デモ HTML Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker ed と sed HTML Raspberry Pi C 言語 命題論理 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||