手続き型のプログラムではループの中に途中経過を保持する変数(アキュームレータ)を使うことが多い。例えば数列の総和を求めるプログラムは次のようになる。 irb(main):001:0> begin irb(main):002:1> total = 0 irb(main):003:1> for i in 1..10 irb(main):004:2> total += i irb(main):005:2> end irb(main):006:1> puts total irb(main):007:1> end 55 上のプログラムの for ループのなかで、総和の途中経過を保持する変数 total がアキュームレータだ。しかし、Haskell ではこのような再代入の方法はないので、別の方法を考えないといけない。一般的には次のようにリストの総和を求める関数を再帰的に定義する。 Prelude> {total [] = 0; total (x:xs) = x + total xs} Prelude> total [1..10] 55 また、foldr や foldl のような畳込み関数を利用すると、擬似的なアキュームレータを記述することができる。それを示す前にまず foldr などの畳込みがどのように実行されるかを見てみる。 Prelude> foldr (\x y -> "(" ++ show x ++ "+" ++ y ++ ")") "0" [1..10] "(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+0))))))))))" Prelude> foldl (\x y -> "(" ++ x ++ "+" ++ show y ++ ")") "0" [1..10] "((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)" アキュームレータはなく、リストのデータがスタックに保存されていって展開の最後に計算されることがわかる。これをよく見ると foldl の x が手続き型のプログラムのアキュームレータ total の役割に近いことがわかる。そこでやってみた。 Prelude> foldl (\total x -> total + x) 0 [1..10] 55 ラムダ記法の本体の total + x のところが for ループの total = total + i に対応しているのがわかる。手続き型のプログラムのループの部分はこのように foldl で置き換えることができるかどうかを考えてみるのもいいかもしれない。たとえば、リストの要素の2乗和をとる計算は次のようになる。 Prelude> foldl (\total x -> total + x*x) 0 [1..10] 385 しかし、これは次のようなプログラムのほうが可読性が高い。 Prelude> sum [x*x| x <- [1..10]] 385 アキュームレータにこだわらずに計算の意味を考えた翻訳のほうも考える必要があるだろう。 追記 数値リストの総和と2乗和を同時に計算するプログラムを考えてみた。アキュームレータを意識したプログラムは次のようになる。 Prelude> foldl (\total x -> (fst total + x, snd total + x*x)) (0,0) [1..10] (55,385) アキュームレータを使わない場合は次のようになる。 Prelude> foldl (\x y -> (fst x + fst y, snd x + snd y)) (0,0) [(x,x*x)| x <- [1..10]] (55,385) アキュームレータを想定したほうが簡潔?
by tnomura9
| 2019-05-19 08:45
| Haskell
|
Comments(0)
|
カテゴリ
新型コロナウイルス 主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude Ocaml ボーカロイド 圏論 jQuery デモ HTML Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker ed と sed HTML Raspberry Pi C 言語 命題論理 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||