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より