tanakh.jp

foldlを直す

Posted on April 7, 2014, Tags: Haskell



http://www.well-typed.com/blog/90/
foldlに関するこの記事︵英文︶が面白かったので、勝手翻訳しました。 foldlなんとかなるといいですね。

foldlを直す


foldl 関数は壊れている。壊れているとみんなが知っている。 四半世紀近く壊れたままだ。ついにこれを修正する時が来た！
今日、私はPrelude.foldlをData.List.foldl'として知られる実装で再定義することを提案する。

foldlは壊れている！


既にご存知だとは思うが、念のため…
Haskellerが必ずfoldlではなく、foldrやfoldl'を使うように勧めてくることにお気づきだろうか？ 例えばReal World Haskellでは次のように言っている。
 
`foldl`のサンクの挙動のため、実アプリではこの関数を使わないようにするのが望ましい。
特に問題がない場合でも、`foldl`の使用は不要なオーバーヘッドを払うことになる。
代わりに`Data.List`をインポートして、`foldl'`を使うこと。
この本のオンライン版の最初のユーザーコメントは次のようなものだった。
 
なんでData.Listのfoldlの実装がPreludeにないんですか？
　
 
追加：なんで`foldl'`がデフォルトじゃないんですか？
いい質問だ。
OK、それじゃあfoldlとfoldl'の違いを話さねばならない。
 
foldl :: (b->a->b) ->b-> [a] -> b
foldl f a []     = a
foldl f a (x:xs) = foldl f (f a x) xs

foldl' :: (b->a->b) ->b-> [a] -> b
foldl' f a []     = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
無味乾燥な技術的な違いは、foldl'は次の再帰呼び出しの前に関数呼び出しを評価するというところだ。 その結果どういう違いが起こるのかはおそらく自明ではないので、 もう少し広い範囲を眺めてみることにしよう。

右畳み込み、左畳み込み


最初にHaskellを勉強したとき、リストの畳み込み方には右からと左からの二つがあると教わったはずだ。
 
foldl f z [x1, x2, ..., xn] = (...((z`f` x1) `f` x2) `f`...) `f` xn

foldr f z [x1, x2, ..., xn] = x1 `f` (x2 `f` ... (xn`f`z)...)
﹁左から﹂あるいは﹁右から﹂というのは、foldlとfoldrが計算するもの、 括弧が左にネストしているか、右にネストしているか、を表している。 実行時にはもちろんリストは左︵先頭︶の要素から見なければならない。
それから、左右の畳み込みについて違った考え方を勉強することになる。 すなわち、左畳み込みはリスト全体を正格に走査する伝統的なループとして使えて、 右畳み込みはデマンドドリブンなイテレータとして使えるということだ。 左畳み込みをこのように使うケースでは、第1引数に対して正格な関数︵例えば(+)︶を渡し、 右畳み込みでは第2引数に対して非正格な関数︵例えば(:)︶を渡す。
実際にはfoldlとfoldrのどちらを使うべきなのかは、 ﹁すべての要素を一度﹂必要とする(foldl)か、 インクリメンタルな、あるいはショートカットの振る舞いが必要か(foldr)によって決めることが多い。

アキュームレータのサンク


これまたHaskellの勉強にて、foldlは次のような頭のおかしい挙動をするのだと教わる。
 
foldl (+) 0 (1:2:3:[])
          =  foldl (+) (0 + 1)             (2:3:[])
          =  foldl (+) ((0 + 1) + 2)       (3:[])
          =  foldl (+) (((0 + 1) + 2) + 3) []
          =            (((0 + 1) + 2) + 3)
ループとして利用する際、こういうことに気を付けなければならない。
 
foldl' (+) 0 (1:2:3:[])
          =  foldl' (+) 1 (2:3:[])
          =  foldl' (+) 3 (3:[])
          =  foldl' (+) 6 []
          =             6
もちろんこれはfoldl'で解決できる。 foldl'では`+の呼び出しは次の再帰呼び出しの前に評価される。

どういう時に(foldl’ではなく)foldlが役に立つのか？


短い答えは﹁そんなことはまずない﹂である。
初心者は、往々にしてfoldlは何らかの意味のある場合があるのだ ︵でなければ、何で両方あるんだ？︶と思い込むものだが、 実際にはそんなケースはないのだとだんだん分かってくる。
まずfoldlの引数fが正格関数だった時、 この場合いずれにせよ最後まで評価しなければならないので、 評価の遅延には全く何の意味もない。 なので、何かご利益があるとすれば関数fの第1引数が非正格な時に限られるが、 それも考えなくてもよい。 なぜなら、普通はまずfoldrが第一候補に挙がるからである。
実際には、関数fの第1引数が非正格であるときでさえ、 おそらく評価の遅延は何の利得も生まないし、 先行評価することによる害もないだろう。 foldlはリスト全体を走査する必要があることを思い出して欲しい。 foldrのショートカット動作はfoldlでは不可能なのだ。
foldl'が過剰に正格だということを示す作為的な例は、作ろうと思えば作れる。 lastとlast'を次のように定義する。
 
last  = foldl  (\_ y ->y) (error "empty list")

last' = foldl' (\_ y ->y) (error "empty list")
これを試してみるとこうなる。
 
> last [1,undefined,3]
3
> last' [1,undefined,3]
*** Exception: Prelude.undefined
これはアキュームレータが常に最後の要素になるが、 ︵最後の一つ以外の︶要素は実際には必要としないためである。
そういうわけで、foldl'がこういうケースで失敗するのは確かだが、 この例はまた、頭の悪い実装でもある。 普通の定義の方がよほどわかりやすい。
 
last [x]    = x
last (_:xs) = last xs
last []     = error "empty list"
foldlでうまく行ってfoldl'ではだめなケースはすべてこうした方がうまく書ける。 つまりそういう例は、作為的なものであるか、あるいは別の書き方をした方が分かりやすい。
時々sumがfoldl'ではなくfoldlで定義されていることを、 これはHaskellの設計者が(+)が遅延であるようなNumのインスタンスを許したいが為の 要求なのだと指摘する人がいる。 全くもってナンセンスである。 そもそもそういうケースではショートカット動作の恩恵を受けるために、 foldlではなくてfoldrを使うべきである。 もっと分かりやすく言えば、sumが定義されたころの初期のバージョンのHaskellには foldl'が用意されていなかったということだ。
Haskellプログラマとしての15年近くの間に、 明確にfoldl'ではなくてfoldlを使う必要があると思ったこと場面が3回ぐらいある。 なぜ正確な回数じゃないのかといえば、正確に思い出せるのがそのうちの1回だけだからである。 その1回が、Webサーバーのキャッシュをアップデートするためのこの 小汚いコードである。 ローカル再帰で書いた方がどう考えても綺麗になるはずだが、 その時の私はfoldlの実利用を思いついた嬉しさのあまりに、 それを使うことを止められなかった。 もちろん間違ってfoldlを使っているわけではないことを示すためにコメントが必要だった。

それでは、なぜfoldlとfoldl’があるのか？


foldlがほぼ間違いなく間違いである︵あるいは、良性の問題である︶というのなら、 どうして第一候補に鎮座しているのだろう。
確かなことは分からないが、私の推測を書いてみよう…
遡ること24年前、Haskell 1.0の発表の日、 当時seq関数のようなものは影も形もなく、 それゆえ、foldlを﹁古典的﹂に定義する以外、選択肢がそもそも存在しなかった。
時は流れ6年後、多くの議論を経てHaskell 1.3にseq関数が入ることになる。 しかしながらHaskell 1.3のseq関数はEvalクラスの一部だったので、どこでも使えるというわけではなかった。 Haskell 1.3では、foldl'は次のような型で定義しなければならなかっただろう。
 
foldl' :: Eval b => (b -> a ->b) -> b -> [a] ->b
Haskell 1.4とHaskell 98はseqからEvalクラスの制約を外すことになったが、 foldlの定義は変わらなかった。 そこでHugsとGHC、その他の処理系は非標準のfoldl'を追加した。
当時の人々は互換性の問題を考えるのが面倒だと考えたのではなかろうか。 非標準のfoldl'を追加することは簡単だが、標準を変えることはそれほどには簡単ではない。
最初からseqが有ったのならば、foldlはそれを使って実装されたのではなかろうか。
MirandaというHaskellの祖先の1つには、Haskell 1.0の5年も前から既にseqが存在していた。

Orwellの正格foldl！


Orwellは興味深い例だ。 Orwellはまた別のHaskellの祖先であり、 Mirandaおよび初期のHaskellに非常によく似ている。 消息筋によれば、Orwellのfoldlは今日foldl'として定義されるもの、すなわち正格評価版だったそうだ。 私はそれを確かめるため、数日オンラインをさまよったが、 Orwellに関する情報は非常に少なかったため、 Philip Wadlerに直接尋ねることにした。 Philは親切にも、私の為にマニュアルを発掘して問題の定義の部分を見つけてくれた。
オリジナルバージョンでは、
 
An Introduction to Orwell
(DRAFT)
Philip Wadler
1 April 1985
In the standard prelude:

lred f a []  =  a
lred f a (x:xs) = lred f (f a x) xs
このように定義されていたが、5年後、Haskell 1.0が公開されるという頃…
 
An Introduction to Orwell 6.00
by Philip Wadler
revised by Quentin Miller
Copyright 1990 Oxford University Computing Lab

In the standard prelude:

foldl :: (a -> b ->a) -> a -> [b] -> a
foldl f a []  =  a
foldl f a (x:xs)  =  strict (foldl f) (f a x) xs
strictという関数が使われているところに注目したい。 おそらく、Orwellのstrict関数は次のように︵あるいはそれと等価に︶定義されていたのだろう。
 
strict :: (a->b) ->a-> b
strict f x =x`seq` f x
︵これは近頃のHaskellでは($!)と呼ばれているものだ。︶
つまり、私の情報が正しいのならば、Orwellはfoldlを正格なバージョンに変更したということだ！
私はこれが正しい決定﹁だった﹂と、そして正しい決定﹁である﹂と主張する。 foldlが修正されなかったのは、単にHaskellへのseqの実装の遅れと、 後方互換性への恐れ及び怠慢が招いた結果に過ぎないのだと主張する。

Just do it!


foldlの修正はData.Listのimportに煩わされて、 ついうっかり出来心でfoldlを使ってしまう我々の助けになるだろう。 また、迷える初心者の助けにもなるはずだ。 さらに、foldlを最初に説明して、なぜそれを決して使ってはならないのか教えなければならない 講師の救いにもなるはずだ。
Orwellはこの過ちを24年前に修正した。 おそらくHaskell 1.0よりも前のことだ。 単なる古い間違いなのだから、 今我々がこれを直さない理由はどこにもない！

後書き‥どっちのfoldl’？


単純な話をややこしくするのは好きではないが、 foldl'の定義としてふさわしいものが2つあることをお断りしておく。 どちらがよりふさわしいのかという真剣な議論を見たことはない ︵これもまた別の歴史的な事故だと疑っている︶。
本文中に引用したバージョンが﹁標準的な﹂バージョンである。 bangパターンを用いて、もう少し綺麗に書くことができる。
 
foldl' :: (b->a->b) ->b-> [a] -> b
foldl' f a []     = a
foldl' f a (x:xs) = let !a' = f a x
                     in foldl' f a' xs
もう一つのバージョンは次の通り。
 
foldl'' :: (b->a->b) ->b-> [a] -> b
foldl'' f !a []     = a
foldl'' f !a (x:xs) = foldl'' f (f a x) xs
一つ目のバージョンは、再帰呼び出しの前にアキュームレータを評価するのに対して、 二つ目のバージョンは呼び出しに際して、アキュームレータを常に︵WHNFまで︶ 評価した状態にしておくという違いがある。
これらの二つはほとんど同じ挙動を示す。 異なる結果になる入力を見つけるのはちょっと手間だが、ここに一つを示す。
 
foldl'  (\_ y ->y) undefined [1] = 1
foldl'' (\_ y ->y) undefined [1] = undefined
標準的なfoldl'は、すべての新しく作ったアキュームレータを評価されるようにするが、 最初に渡された値は依然として評価しなくてもよい。 別のバージョンでは、アキュームレータは常に評価されることが伺える。
二つ目のバージョンは、コード生成という観点からは魅力的である。 GHCがfoldl'に対して︵そして正格関数を渡されたときに︶行える賢い最適化の一つに値のunbox化があり、 これにより例えばIntをInt#にunboxして、引数をヒープではなくレジスタで渡すことができる。 標準的なバージョンのfoldl'では、ループの初回のみ、特別ケースとして扱わなければならない。 なぜならば、アキュームレータがまだ評価されていないかもしれないからである。 foldl''ではそういう心配はない。 最初のイテレーションから正しくunbox化できる。 もっとも、GHCは大抵の場合は初期値が常に評価されるかどうかを推論することができるが、常にではない。
︵Don Stewartと私は数年前、リストのstream fusionの作業中にこれに気づいた。 ストリームに対するfoldl'を二つ目のバージョンに対応する形で実装して、 そして、標準リスト関数との正格性の比較テストの実行中に失敗した。︶
そういうわけで、foldlを正格バージョンに修正しようとするなら、 ﹁最初のイテレーション以降を正格に﹂バージョンではなく、 完全正格バージョンにするべきかもしれない。


comments powered by Disqus