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);
となる