読者です 読者をやめる 読者になる 読者になる

師曰く、畳込み関数は偉大なり

そういえば、以前、右畳込み関数 foldr さえあれば他は要らない!との主張を聞いたことがあるのですが*1、遅延評価しない処理系で、foldr って何かうまみがあるのか、どなたか教えてくださいませんでしょうか……。

畳込み関数 foldr, foldl がどんなものなのかは、[ruby-dev:11595] accumulator, Enumerable#{foldr,foldl} あたりをご参照くださいませ。引用させていただくと:

 [a1,a2,...,an].foldl(a0){|x,y| f(x,y)}
 => f(f(...(f(a0,a1),a2)...))
 
 [a1,a2,...,an].foldr(a0){|x,y| f(x,y)}
 => f(a1,f(a2,f(...,f(an,a0))))

foldr は(cons セルで実現している場合の)リストのデータ構造をそのまま関数適用に置換できることが魅力ではありますが、再帰で実装しないといけませんよね?遅延評価できるのならば、無限リストという決定的な使い道があるんですが。

というわけで、言語が(どちらかといえば)専門といいつつも、うろ覚えだらけでぜんぜん専門的ではない自分なのでした。

*1:foldr で map も filter も作れます。