foldr の本質は再帰関数だ。foldr の計算を展開してみると、 foldr (*) 1 [1..5] = (1*(2*(3*(4*(5*1))))) = 120 だが、これは次の再帰関数の計算と同じものだ。 foo [] = 1 foo (x:xs) = x * foo xs foo [1..5] = (1*(2*(3*(4*(5*(1)))))) = 120 つまり、foldr は一種の無名再帰関数として使うことができる。そこで、length 関数を foldr でプログラムしてみた。 Prelude> foldr (\x y -> 1+y) 0 [1..5] 5 foldr の計算を展開すると、これは次のような計算をしていることがわかる。 foldr (\x y -> 1+y) 0 [1..5] = (1+(1+(1+(1+(1+0))))) = 5 同じような発想でリストの2乗和の計算もできる。 Prelude> foldr (\x y -> x*x + y) 0 [1..5] 55 この場合、次のような計算が行われていることになる。 foldr (\x y -> x*x + y) 0 [1..5] = (1+(4+(9+(16+(25+0))))) = 55 これは次のような普通の発想の計算でも確認できる。 Prelude> sum $ map (\x -> x*x) [1..5] 55 二項演算子 + を : に変えると、リストの各要素を2乗することもできる。 Prelude> foldr (\x y -> x*x : y) [] [1..5] [1,4,9,16,25] foldr の計算が再帰関数の計算と同じことがわかれば、foldr が不可解な関数どころか無名再帰関数を記述できる使い勝手のいい道具であることがわかる。 おまけで、reverse を foldl でプログラムすると次のようになる。 Prelude> foldl (flip (:)) [] [1..5] [5,4,3,2,1] (flip (:)) [] 1 = 1:[] = [1] であることを考えて、flip (:) を * で表すことにすると、 foldl * [] [1..5] = ((((([] * 1)*2)*3)*4)*5) = (((([1]*2)*3)*4)*5) = (((([2,1])*3)*4)*5) = ... = ([4,3,2,1]*5) = [5,4,3,2,1] となることを確かめることができる。
by tnomura9
| 2018-10-24 05:26
| Haskell
|
Comments(0)
|
カテゴリ
新型コロナウイルス 主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude Ocaml ボーカロイド 圏論 jQuery デモ HTML Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker ed と sed HTML Raspberry Pi C 言語 命題論理 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||