Common Lispでfoldrを書いてみる

Haskellのfoldrに的を絞ってCommon Lispで説明する。適用条件は狭まるものの、アルゴリズムを再帰関数で抽象化するためのテンプレートっぽさを実感してもらえればと思う(正格評価と遅延評価の違いは無視する)。

まず、foldrをCommon Lispで速度とか考えず素直に書いたらこうなる。

(defun fold-right (fun lst init)
  (if (null lst)
      init
      (funcall fun (first lst) (fold-right fun (rest lst) init)))) 

テキトーに色付けしてみた。funがそのまま適用できないのは、Schemeみたいに関数と変数の名前空間が同じではないから。これのどこが嬉しいかというと、色々な再帰関数のテンプレートになれるところ。たとえば、Common Lispではあまりありがたみがないけど、list内の数字の和を求める関数sumを再帰関数で書いたらこうなる。

(defun sum (lst)
  (if (null lst)
      0
      (+ (first lst) (sum (cdr lst)))))

上のfold-rightに対応する色で色付けしてみた。つまり、(sum lst) = (fold-right #'+ lst 0)となる。funとinitは、固定だからsumでは見えないわけだ。

次に、みんな大好き階乗(n!)の関数factを再帰関数

(defun fact (lst)
  (if (null lst)
      1
      (* (first lst) (fact (cdr lst)))))

見比べると、(fact lst) = (fold-right #'* lst 1)となる。

どんどんいこう、要素数を求める関数length

(defun length (lst)
  (if (null lst)
      0
      (+ 1 (length (cdr lst)))))

見比べると、(length lst) = (fold-right (lambda (x y) (1+ y)) lst 0)になる。ラムダ式でx使ってないって警告出されたりするから、(fold-right (lambda (x y) (declare (ignore x)) (1+ y)) lst 0)としたほうがよさそう。

最後は、標準関数append

appendは、(append '(a b c) '(d e f)) => (a b c d e f) となる関数

(defun append (lst1 lst2)
  (if (null lst)
      lst2
      (cons (first lst) (append (cdr lst) lst2))))

と書ける。対応は、(append lst1 lst2) = (fold-right #'cons lst1 lst2)になる。

今回、foldrがどのような意味であるかを説明した。全ての再帰関数がこの形になるわけではないが、「Haskellで話題に出てくるfoldrって、Common Lispではどういうことなの?」には答えられたかと思う。ちなみに、Common Lispの場合、実際にはreduce使った方が良いみたいだ。

(defun fold-right-reduce (fun lst init)
  (reduce fun lst :from-end t :initial-value init))

Fold (higher-order function) - Wikipedia, the free encyclopediaより