foldrとfoldlのメモ
foldr,foldlのサンプル
foldr (-) 4 [1, 2, 3] -- 1 - (2 - (3 - 4)) == -2 foldl (-) 1 [2, 3, 4] -- ((1 - 2) - 3) - 4 == -8
perlで実装
sub foldr{ my ($func,$init,@list) = @_; my ($x,@rest) = @list; return $init unless $x; $func->($x,foldr($func,$init,@rest)); }
foldr($func,4,(1,2,3))は 以下のように展開
- $func->(1,foldr($func,4,(2,3)));
- $func->(1,$func->(2,foldr($func,4,(3))));
- $func->(1,$func->(2,$func->(3,foldr(4,4,()))));
- $func->(1,$func->(2,$func->(3,4)));
$funcがsub{$_[0]+$_[1]}の場合
(1+(2+(3 + 4)))
となる
sub foldl{ my ($func,$init,@list) = @_; my ($x,@rest) = @list; return $init unless $x; foldl($func,$func->($init,$x),@rest); }
foldl($func,1,(2,3,4))は以下のように展開
- foldl($func,$func->(1,2),(3,4));
- foldl($func,$func->($func->(1,2),3),(4));
- foldl($func,$func->($func->($func->(1,2),3),4),());
- $func->($func->($func->(1,2),3),4);
$funcがsub{$_[0]-$_[0]}の場合
((((1-2) - 3) -4);
となる