手続き的なscanlの説明
foldの動作をｘへの代入、再代入と捉えると分かりやすくなります。
直接foldの動きを見るのではなく、
まずscanlの動作を見てみます。
scanlの型は
Prelude> :t scanl
scanl :: (a -> b -> a) -> a -> [b] -> [a]
となっています。
scanlは、２引数の関数と初期値と何らかのリストを引数にとり、リストを返す関数です。
実際に動かしてみましょう。
Prelude> scanl(\x y -> x + y) 0 [1..3]
[0,1,3,6]
scanlが内部で何をやっているのか想像してみます。
まずscanlが呼び出されたとき、変数ｘに初期値、（この場合は「０」）を代入します。
次に変数ｙにリストの最初の要素（この場合は「１」）を代入します。
次にｘ＋ｙを計算して結果の「１」をｘに再代入します。
次にｙにリストの次の要素「２」を代入し、ｘ＋ｙを計算します。この時ｘは１になっていますので, 結果は「３」です。これをｘに再代入します。
次にｙにリストの次の要素「３」を代入し、ｘ＋ｙを計算します。この時ｘは３になっていますので,結果は「６」です。これをｘに再代入します。
リストの終わりに到達したので、リスト[0,1,3,6]を出力して終了します。
scanlはｘに値が代入された時はすべてその値をリストに保存するようです。
こう見ますとfoldlはscanlと動作は同じで終了時にｘの値のみを出力して終了する、と捉えることができます。
Prelude> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
foldlの型です。
同様にscanrの動作もみてみます。
scanrはxとyの役割が逆転しており、リストの作り方も異なっています。
Prelude> scanr (\x y -> x / y) 2 [3..5]
[1.875,1.6,2.5,2.0]
pythonで動きを追ってみると
>>> x=5.
>>> y=x/y
>>> y
2.5
>>> x=4
>>> y=x/y
>>> y
1.6
>>> x=3
>>> y=x/y
>>> y
1.875
代入、再代入はｙに対しておこなわれます。
ｙに代入があった時、リストの先頭に値を保存します。
Prelude> 1.875:1.6:2.5:2.0:[]
[1.875,1.6,2.5,2.0]
haskellはソースコード上での、変数への値の再代入を許していません。
そのため繰り返しのための構文が用意されていません。
それが可能な言語、例えばPythonでは次のようなコードが書けます。
x=0
for y in [1,2,3]:
x=x+y
print x
これは上記の説明のfoldと全く同じです。
つまりfoldは一般的な言語の繰り返し処理をHaskellで書くための一つの方法になっているわけです。
（PythonのFor文は他の凡百の言語のFor文とはまったく異なります。どちらかというとMapに近い。ただ書き換えのできるグローバル変数も使えるので非常に自由度が高い。）
fold を手続き的にとらえると考えやすくなる処理があります。
Data.List モジュールには insert という関数が用意されています。
Prelude Data.List> :t insert
insert :: Ord a => a -> [a] -> [a]
ソート済みのリストに一つ要素を加えてソート順を崩さずに新たなリストを返す関数です。
他の関数が一般的なリスト処理の関数なのに比べてやや特殊な感じがあります。
たぶん「挿入ソートを実装してください」というメッセージだと思います。
挿入ソートは再起でも書けるとは思うのですが、いきなり fold を使ったほうがわかりやすい。
Prelude Data.List> foldl (\x y -> insert y x) [] [2,7,4,0]
[0,2,4,7]
まず初期値は空リストです。
ｘ に 代入されます。
ｙ には リストの第一要素が代入されます。
ｘ ｙ をひっくり返して insert 関数を適用します。
結果 ｘ に [2] が ｙ に ７ が代入されます。
７ を [2] に insert し [2,7] ・・・・（略）
この操作をリストの終わりまで繰り返します。 これでソート完了。
flip を使って書き直すと
Prelude Data.List> foldl (flip insert) [] [2,7,4,0]
[0,2,4,7]
さらに
Prelude Data.List> foldr insert [] [2,7,4,0]
[0,2,4,7]
foldl と foldr では動作が異なりますが、この場合は結果は同じです。
も参照ください。
0 件のコメント:
コメントを投稿