foldrトリック
foldrは構造の要素に次々に関数を適用していく畳み込み関数の一つ。foldr (☆) '王' "遊戯"とすると'遊' ☆ ('戯' ☆ '王')のように右結合の形になる。 code:haskell
foldr :: Foldable f => (a -> b -> b) -> b -> f a -> b
さて、例えば数値の総和を求めたいときなどにfoldr (+) 0のようにすると、1 + (2 + (3 + (4 + .. と、大量の未評価の式が作られ効率が悪い(代わりにfoldl'を使うべきである)。しかしその事実が拡大解釈されfoldrがfoldl'の下位互換のように見られることがしばしばある。
だが待ってほしい。foldrの結果を関数にしてはいけないという決まりはない。以下のようにすれば、累積する値を正格に評価するような振る舞いが表現できる。実際、foldl'はこのようにして定義されている。
code:haskell
foldr (\x cont -> \acc -> cont $! acc + x) id 1,2.3..10 0 foldl' f r xs = foldr (\x cont acc -> cont $! f acc x) id xs r
複数の値を累積させたり畳み込みを中止するのも簡単にでき、色々応用が効くので「foldrトリック」と名付けた。
foldrのステップ関数は２引数関数で渡さないとインライン展開がうまくいかないので注意する必要がある。