Lisp的直積集合
可変なループ構造を必要とする問題*1に関しては、再帰やスタックを使って可変なループ構造に対応するのがプログラミングの常套手段ですが、そのような手段がそもそも必要になるのは、for文を動的に増やせないという問題に絡んでいます。それじゃfor文を動的に増やせばいいのではないか、と考えるかもしれませんが、CやJavaなどのevalがない言語ではそんなことできません。
ところが我らのLispにはevalがあります。しかもデータ構造がプログラムテキストであるため、動的にプログラムテキストを生成しても不自然に見えません*2。それでは、n個の集合から直積集合を生成する関数を例にとって考えましょう。
直積集合とは{1,2}と{3,4}から生成された{(1,3), (2,4)}{(1, 3), (1, 4), (2, 3), (2, 4)}ことを言います。詳しくはWikipediaを参照してください。
通常、直積集合を求める関数は二つの集合を取りますが、ここでは少し拡張してn個の集合を取れるようにします。礼儀正しく実装するなら、次のように、まず二つの集合の直積集合を求める関数を定義して、次にその関数を利用してn個の集合の直積集合を求める関数を定義することになるでしょう。
defun flatten (a) (if (nlistp a) (list a) (apply 'append (mapcar 'flatten a)))) ;; 二つの集合の直積集合を求める関数 (defun product (s1 s2) (let (result) (dolist (a s1) (dolist (b s2) (push (flatten (list a b)) result))) (nreverse result))) ;; n個の集合の直積集合を求める関数 (defun product-list (&rest list) (if (null list) list (let ((a (car list))) (dolist (b (cdr list)) (setq a (product a b))) a)))
実装がシンプルなのは良いですが、効率が少し悪そうに思えます。
それではevalを使った方法で実装してみましょう。今回のエッセンスは上記のproduct関数の二つの(dolist ...)に注目して、このループ構造を動的に拡張することです。
まず内側の(dolist ...)あるいは(push ... result)を生成するproduct-form関数を定義します。
(defun product-form (n len syms) (if (eq n len) `(push (list ,@(reverse syms)) result) (let ((sym (intern (format "x%s" n)))) `(dolist (,sym (nth ,n list)) ,(product-form (1+ n) len (cons sym syms))))))
この関数は三つの引数を取ります。第一引数は処理中のリストの要素番号、第二引数は集合のリストの長さ、第三引数は現在保持しているシンボルのリストです。始めのif文で、nがリストの長さと同じなら(push ... result)を生成し、そうでなかったら(dolist ...)で一段深いproduct-formを囲むようにしています。(dolist ...)でバインドされるシンボルは適宜x0, x1, x2のような名前を与えられてsyms変数に追加されていきます。
実際の実行結果は以下のようになります。
(product-form 0 3 nil) ;; (dolist (x0 (nth 0 list)) (dolist (x1 (nth 1 list)) (dolist (x2 (nth 2 list)) (push (list x0 x1 x2) result))))
これは長さが3のリストのループ構造を表わしています。あとは、これを利用してn個の集合の直積集合を求める関数を定義するだけです。
(defun product-list (&rest list) (let (result) (eval (product-form 0 (length list) nil)) (nreverse result)))
実行結果を示します。
(product-list '(1 2 3) '(4 5 6) '(7 8 9)) ;; ((1 4 7) (1 4 8) (1 4 9) (1 5 7) (1 5 8) (1 5 9) (1 6 7) (1 6 8) (1 6 9) (2 4 7) (2 4 8) (2 4 9) (2 5 7) (2 5 8) (2 5 9) (2 6 7) (2 6 8) (2 6 9) (3 4 7) (3 4 8) (3 4 9) (3 5 7) (3 5 8) (3 5 9) (3 6 7) (3 6 8) (3 6 9))
プログラムの長さとしては前者・後者とも差がないように感じます。実行効率としては、ちゃんと実装すれば後者のほうが速くなるでしょう。もちろんJITなどが効く言語では前者のほうが良いでしょうが。
結論としては、プログラムもデータ構造として扱えるLispでは、このエントリで紹介したような手法が意外に有効だと言えます。読み易さの点では課題が多いかもしれませんが、複雑なアルゴリズムを書くよりこちらの手法のほうがわかりやすくなるケースは少なからずあると思います。
