2014/12/31

カテゴリー : , , , ,

ClojureでunfoldとHylomorphism

unfold

 unfoldは, fold(reduce)の双対として定義される関数で, リストを生成する一種のジェネレータのような働きをするものです. 畳み込み関数に対応する, 要素を展開する関数とみなすことができます. Clojureだとiterateが一番近い関数でしょう.
user> (take 10 (iterate (partial + 2) 0))
(0 2 4 6 8 10 12 14 16 18)
 Haskellでは, foldが二種類あり, foldrとfoldlで, 右から畳み込みと左から畳み込みに対応しています. Clojureのreduceは, foldlに相当します. そして, foldr/foldlそれぞれにunfoldr/unfoldlが定義できますが, 以下の文章では, foldlを前提に話を進めます. (Haskellのfoldとunfoldrについてはここで書いています.)

 unfoldlをClojureで書くとしたら以下のような感じになると思います.
(defn unfoldl [pred g h start]
   (map g (take-while #(not (pred %)) (iterate h start))))
 計算を始めるオブジェクトと繰り返し適用するh, 生成したリストにmapをかけるためのgと, リストを終わらせる条件式predからなります. map gがtake-whileよりも後の処理になるのも重要な点です.

Hylomorphism

 Hylomorphismとは, (代数的データ型へ)一般化されたfoldとunfoldの合成のことで, リストにおけるfoldlとunfoldlについて,

hylol f e p g h = foldl f e . unfoldl p g h

と書ける関数です. (太字部分 2015/01/08追記) unfoldlで生成したリストをfoldlで畳み込むような計算になります. map/reduceならぬ, generate(リスト生成)/map/reduceの処理が一つにまとまりました. Clojureだと次のようになります.
(defn hylol1
  "hylol f e p g h = foldl f e . unfoldl p g h"
  [f init pred g h start]
  (reduce f init (unfoldl pred g h start)))
 これだけだと, 抽象的な関数を組み合わせたまた別の抽象的なだけの関数といった印象しか残りません. しかし, Hylomorphismは, これを別のリストを使わないコードへ書き直すことができるのです.
(defn hylol2
  [f e p g h b]
  (if (p b)
    e
    (f (g b) (hylol2 f e p g h (h b)))))
 これが, HylomorphismLの別の実装です.

 foldlとunfoldlを組み合わせると当然, unfoldlで生成されたリストが, foldlにおいて, 畳み込まれてしまうため, 結果的に, 最終的な計算結果(戻り値)に不要なリストを計算途中で生成する必要が出てきてしまいます. しかし, 上記の2番目の実装では, リストを生成する様子がありません.

 Hylomorphismの変換では, foldとunfoldの合成関数を, これと同等の意味を持つ｢リストを生成しないプログラム｣へ書き換えることでプログラムを高速化します. この辺はmap分配則と同じような感じですね.

 例えば, 1〜100の和を計算するようなプログラムについて, foldl/unfoldlを使って,
(defn sum-from1to [n]
  (reduce + 0 (unfoldl (partial = 0) identity dec n)))
 と書けるわけですが, これをHylomorphismで書きなおしてみると, hylol2の実装を使って,
user> (hylol2 + 0 (partial = 0) identity dec 10)
55
と書けます. これをhylol2の実装へ展開すると,
(defn hylol2-sum
  [b]
  (if ((partial = 0) b)
    0
    (+ (identity b) (hylol2-sum (dec b)))))
 のように書きなおすことができて, foldl/unfoldlを使った場合に比べて素直な書き方になっていることがわかるかと思います.

 ある意味では, Hylomorphismの変換とは, リストを使って抽象化した処理を, 素朴な再帰関数に書き戻す手法だとみなすことができます.

Hylomorphismの変換例

 さて, Hylomorphismの変換に関する一番の関心事は, 本当に高速化するのかという点と, 具体的にプログラムへ適用できるのかという点です. というわけで, 以下は, 8Queen問題のプログラムでHylomorphismを使ってみたケースです.

 前に書いた記事の8Queen問題の解法では, バックトラックにより計算していましたが, 今回は, 素朴な総当り法を使います.

 8Queen問題の解とは, 究極的には, 1〜8の数字の並び, だとみなすことができます. 例えば, x座標を固定した場合, 鳩の巣論法的に, 各x座標(= 1, 2, ... 8)には必ず一つQueenが入っている必要があるからです. というわけで, x座標の情報は不要になり, 順序を持ったy座標列が, 解となります.

 というわけで, このプログラムでは, y座標のpermutationを与え, そこから, xy座標の組を計算し, その座標列が正しいかどうかを判定し, 正しければ解を返します. 以下がコードです.
(use 'clojure.math.combinatorics)

;; unfoldl & hylomorphism
(defn unfoldl [pred g h start]
   (map g (take-while #(not (pred %)) (iterate h start))))

(defn hylol2
  [f e p g h b]
  (if (p b)
    e
    (f (g b) (hylol2 f e p g h (h b)))))

;; 8 queen
(defn conflict? [x y others]
  (and (not (empty? others))
       (let [x1 (ffirst others) y1 (second (first others))]
         (or (= x x1) (= y y1)
             (= (- x x1) (- y y1)) (= (- x x1) (- y1 y))
             (conflict? x y (rest others))))))

(defn not-conflict? [ls]
  (let [xy (first ls) others (rest ls)]
    (not (conflict? (first xy) (second xy) others))))

(defn andf
  ([a] a)
  ([a b] (and a b)))

(defn correct-answer? [arrangement]
  (reduce andf
    (map not-conflict?
      (take-while first (iterate rest arrangement)))))

(defn correct-answer?-v2 [arrangement]
  (hylol2 andf true #(not (first %)) not-conflict? rest arrangement))

(defn check-and-cons [checker yss]
  (let [arrangement (map list (range 8) yss)]
    (if (checker arrangement) arrangement [])))

(defn get-correct-answers [permutations checker]
  (filter first (map (partial check-and-cons checker) permutations)))

(def perm (doall (permutations (range 8))))

(def correct-answers
  (get-correct-answers perm correct-answer?))

(def correct-answers-v2
  (get-correct-answers perm correct-answer?-v2))
 実行時間を計測してみると, 確かに高速化されていることがわかります. correct-answersの方が, foldl/unfoldl(に相当するもの)を使った場合で, correct-answers-v2がhylol2によりプログラム変換を行ったケースです.
user> (time (count correct-answers))
"Elapsed time: 733.504269 msecs"
92
user> (time (count correct-answers-v2))
"Elapsed time: 592.678338 msecs"
92
 上記の結果を見た場合, それ以外の部分でボトルネックになっている部分もありそうですが, Hylomorphismの変換により, 一応, 高速化ができていることが観察できました.

 さて, 問題のプログラム変換は以下の部分で行っています. correct-answer?が, 素朴なfoldl/unfoldlで, correct-answer?-v2がリストを生成しないHylomorphismを使ったコードになります. correct-answer?の方にunfoldlというキーワードは見当たりませんが, map/take-while/iterateの組み合わせがそれに相当します.
(defn correct-answer? [arrangement]
  (reduce andf
    (map not-conflict?
      (take-while first (iterate rest arrangement)))))

(defn correct-answer?-v2 [arrangement]
  (hylol2 andf true #(not (first %)) not-conflict? rest arrangement))
 ここでは, [[1 2] [3 4] ...]のようなQueenの位置を表すリスト(arrangement)を受け取り, そこから, 部分リストを生成し(iterate/take-while), 各部分リストの｢先頭の要素｣と｢他の要素｣が衝突しないか(互いが取り合える位置にいないか)をチェックして(map not-conflict?), 矛盾しているケースがないかどうかをandf(andの関数版)で確認し(reduce), その答えの正解/不正解をboolで返すというものです.

 例えば, 座標のリスト[p1 p2 ... p8]があるときに互いに衝突していないかを判定するためには, p1と[p2 ... p8], p2と[p3 ... p8], p3と[p4 ... p8]と判定していくため, 上記のようなrestをiterateする実装になっています.

 reduce, map. take-while, iterateが一堂に会しているので, 図らずともHylomorphismの変換が簡単にできました.

 Hylomorphismの変換から得られる教訓(?)は, プログラム中に, ジェネレータによるリスト生成を行う部分があり, その先で, reduce(畳み込み関数)がそのリストを畳もうと待ち構えているとき, そのコードは, リストを使わないコードへ書き換えることができるかもしれない, ということです. そして, 書き換えたコードは, 余分な(本来の計算結果に不要な)データ構造の生成が不要になることで, 高速化できる筈だという結論です.

参考文献
  • 関数プログラミングの楽しみ, Jeremy Gibbons & Oege de Moor(編集), 山下 伸夫 (翻訳), オーム社, 2010/6/23
    • ifphの続編(?), この記事の内容は本書のhylomorphismのセクションを元にかかれています.
  • 構成的アルゴリズム論
    • hyloだけでなく, map分配則などプログラム運算の様々な規則が紹介されています. チュートリアル.
  • Anamorphic Adventure in Clojure - Matlux
    • Clojureで, Anamorphism(unfold相当)を定義する話. 

0 件のコメント :

コメントを投稿