2011/10/30

foldパターン

flatten

CommonLispで

 ((a . b) (c . d))

というconsリストのリストを

 (a b c d)

というリストに直すコードを書きたいわけ。

この問題、入力が「ネストしたリスト」であれば、つまり ((a b) (c d)) を (a b c d) にする、という問題であれば、Lisp組み込みのリスト処理関数を 使ってほぼワンライナーで書ける。

(defun flatten-nested-list (nlist)
  (if (listp nlist) (mapcan #'flatten-nested-list nlist) (list nlist)))

が、この設問での入力はcdrにリストではなくアトムが来るケースを処理しないと ならない。最後がnilでないリスト (dotted list) というのははみ出し者で、 標準の便利なリスト関数はdotted listを想定してないものが多く、うまく扱えない。 これはむしろcarとcdrに分岐する二分木と考えるのが良い。

二分木を深さ優先で再帰していって、順番に出会ったアトムを数珠つなぎに してゆく、と考えれば、こういうコードになる。(consは尻尾からつないでいかないと ならないので、cdr方向に最初に再帰していることに注意)

(defun flatten-tree (tree)
  (labels ((rec (tree seed)
             (cond ((null tree) seed)
                   ((consp tree) (rec (car tree) (rec (cdr tree) seed)))
                   (t (cons tree seed)))))
    (rec tree nil)))

「途中の計算結果を受け渡しながら、木を深さ優先で再帰してゆく」という制御の流れは、 「計算の初期値seed」と「ひとつの要素と途中結果から新たな途中結果を求める計算proc」 をくくりだせば、パターンとして抽象化できる。

(defun fold-tree-right (proc seed tree)
  (labels ((rec (tree seed)
             (cond ((null tree) seed)
                   ((consp tree) (rec (car tree) (rec (cdr tree) seed)))
                   (t (funcall proc tree seed)))))
    (rec tree seed)))

これを使うと、flatten-treeはワンライナーだ。

(defun flatten-tree (tree) (fold-tree-right #'cons nil tree))

また、例えば「木の中にある数字全ての和を求める」なんてのもワンライナーで書ける。

(defun sum-tree (tree) (fold-tree-right #'+ 0 tree))

(sum-tree '((1 . 2) (3 (4) . 5))) => 15

この、seedで中間結果を回しつつ再帰してゆくパターンはとても良く見かけるので、 慣れておくと便利。

Tags: Lisp, Programming