2012/03/14

fold, fold-left, fold-right

• Scheme「foldとfold-rigt」

foldとfold-rightが左/右結合ってのはその通りなんだけれど、 畳み込まれる演算の引数の順序に注意が必要。

(fold op 'z '(a b c d))         (fold-right op 'z '(a b c d))

     op                                     op          
    /  \                                   /  \
   d    op                                a    op
       /  \                                   /  \
      c    op                                b    op
          /  \                                   /  \
         b    op                                c    op
             /  \                                   /  \
            a    z                                 d    z

左結合の方が関数型言語での主流の定義とはちょっと違う。 Haskellのfoldlに対応するのはR6RSで定義されているfold-leftの方。

(fold-left op 'z '(a b c d))    (fold-right op 'z '(a b c d))

             op                             op          
            /  \                           /  \
           op   d                         a    op
          /  \                                /  \
         op   c                              b    op
        /  \                                     /  \
       op   b                                   c    op
      /  \                                          /  \
     z    a                                        d    z

op が可換な演算ならfoldもfold-leftも変わらないんだけど。

図示するとfold-left/fold-rightの方が綺麗に対称になってる。 ただ、実用的な場面ではfoldの方が使いでがある、気がする。多分、 「頭からリストの要素を見つつ、結果をconsしてゆく」っていうSchemeで よくあるループのパターンがfoldで実現されてるからじゃないかな。

とはいえ他の言語のアルゴリズムを持ってくる時に混乱が生じがちなので、 さっきGaucheにもfold-leftを足しといた。

Tags: Programming, Scheme