Clojure を学ぶ

この記事は旧ブログの以下の記事を書き直したものです。

参考1: 数を並びかえる(1)
参考2: 数を並びかえる(2)
参考3: 数を並びかえる(3)

今年(2017)の正月に本屋で

プログラミング Clojure 第2版、(Stuart Halloway and Aaron Bedra 著、川合史朗 訳、オーム社)

をみつけて写経しつつざっと読みました。新しい言語なので進化が速くこの本のコードを写経しているとライブラリのバージョンが合わなくて結局古いバージョンをインストールすることになりました。今調べたら原著の第3版が出ているようなので英語版でよければこちらを読むほうがいいでしょう。邦訳も待たれます。

https://pragprog.com/book/shcloj3/programming-clojure-third-edition

説明は旧ブログの記事を読んでいただくとしてコードを中心に移転しますが、大きく変えた点は置換をそのまま \(S_n\) として見てしまおうという点です。

つまり \(S_{n}\) は関数の集合なので、例えば \(S_{3}\) なら

[#function[user/make-fn/fn--20073]
 #function[user/make-fn/fn--20073]
 #function[user/make-fn/fn--20073]
 #function[user/make-fn/fn--20073]
 #function[user/make-fn/fn--20073]
 #function[user/make-fn/fn--20073]]

こういう集合を返すのが正しいのですが、これでは見た目で意味がわからない。見た目としては

([1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1])

のほうがいいと思うわけです。ここで例えば [2 3 1]\(1 \mapsto 2,\ 2 \mapsto 3,\ 3 \mapsto 1\) という関数を表すことにします。恒等関数は明らかに [1 2 3] です。

旧ブログでは「正しく」やろうと思ったので、いちいち置換に戻して表示したり面倒なことになっていました。混乱の元になるので良くないのはわかっていますが、コードがすっきりする良さもあるので今回はこの方針でいきます。

以下

(def S3 (permutation [1 2 3]))
(def S4 (permutation [1 2 3 4]))

とします。

参考1: 数を並びかえる(1) より

(defn range1-n [n] (range 1 (inc n)))

(defn permutation [coll]
  (let [coll (vec coll)
        n (count coll)
        idx (vec (for [j (range n)] (symbol (str "i" j))))
        lst (take n (repeat coll)) ; vector にする必要なし
        args (vec (interleave idx lst))]
    (eval `(for ~(conj args :when `(= (count (set ~idx)) ~n)) ~idx))))

参考1permutationinto [] のところが veciterate identity のところが repeat に変わっています。

参考1では lisp と違うのは , のかわりに ~ を使うことだけ と書きましたが不十分と思うので Wikipedia の記事も引用しておきます。

https://ja.wikipedia.org/wiki/Clojure

Clojure言語のマクロ機構は、Common Lispのそれによく似ている。ただし、Clojure言語のバッククオート(「シンタクス・クオート」と呼ばれる)では、個々の記号が局所的な名前空間によって区別されるという点で、Common Lispのマクロとは異なっている。この仕組みによって、マクロ展開時の変数の捕獲(= マクロが展開された環境に同名の変数があると、その変数の値が変更されてしまうこと)を避けている。マクロ展開時の変数の捕獲を許容するように強制することもできるが、それは明示的に行わなければならない。また、Clojure言語では、現在の名前空間にインポートされた別の名前空間の大域名を変更することは許容されていない。

参考1では置換をクロージャに変換して \(S_{n}\) を作っていましたが、今回は計算するときのみ関数に化けてもらいます。

(defn as-fn [p]
  (fn [i] (p (dec i))))

参考2: 数を並びかえる(2) より

as-fn によって置換の積を

(defn product [& pp]
  (let [fns (mapv as-fn pp), v1-n (range1-n (count (first pp)))]
    (mapv (apply comp fns) v1-n)))

とし、逆関数を

(defn inverse [p]
  (mapv #(inc (.indexOf p %)) (range1-n (count p))))

とします。使ってみると

(product [1 3 2] [2 3 1])
=> [3 2 1]

(inverse [2 3 1])
=> [3 1 2]

(product [2 3 1] (inverse [2 3 1])) ; x x^{-1} = id
=> [1 2 3]

となります。

その他の関数:

(defn inversion-number [permutation]
  (loop [coll permutation result 0]
    (if (empty? coll) 
      result
      (let [f (first coll) r (rest coll)]
        (recur r (+ result (count (filter #(> f %) r))))))))

(defn even-permutation? [permutation]
  (even? (inversion-number permutation)))

(defn odd-permutation? [permutation]
  (not (even-permutation? permutation)))

(defn set= [X Y]
  (= (set X) (set Y)))

set=参考2sg= です。一応、\(S_{n} = S_{n}^{-1}\) を確かめておきます:

(set= S3 (map inverse S3))
=> true

(set= S4 (map inverse S4))
=> true

参考3: 数を並びかえる(3) より

以下

(def A3 (filter even-permutation? S3))
(def A4 (filter even-permutation? S4))

とします。

A3
=> ([1 2 3] [2 3 1] [3 1 2])

A4
=>
([1 2 3 4]
 [1 3 4 2]
 [1 4 2 3]
 [2 1 4 3]
 [2 3 1 4]
 [2 4 3 1]
 [3 1 2 4]
 [3 2 4 1]
 [3 4 1 2]
 [4 1 3 2]
 [4 2 1 3]
 [4 3 2 1])

共役、軌道、共役類分解:

集合演算を使いたいのでロードしておきます。

(use '[clojure.set :as set])

(defn conjugate [x y] ; y x y^{-1}
  (product y x (inverse y)))

(defn orbit [x G]
  (set (map #(conjugate x %) G)))

(defn classify [G]
  (loop [result (), H (set G)]
    (if (empty? H)
      result
      (let [O (orbit (first H) G)]
        (recur (conj result O)
               (set/difference H O))))))

参考3classify は内包表記を使って一行で書けたのですが、計算量が最悪で書き直したかったのです。今回の classify はまずまずの性能で、この部分が今回の記事のメインです。

後は適当に

\(D(G) := \{xyx^{-1}y^{-1} | x,y \in G\}\)

(defn D [G]
  (distinct (for [x G, y G] (product x y (inverse x) (inverse y)))))
  
(D S3)
=> ([1 2 3] [2 3 1] [3 1 2])

(D S4)
=>
([1 2 3 4]
 [1 3 4 2]
 [1 4 2 3]
 [3 2 4 1]
 [4 2 1 3]
 [2 1 4 3]
 [2 3 1 4]
 [4 3 2 1]
 [3 1 2 4]
 [4 1 3 2]
 [3 4 1 2]
 [2 4 3 1])

いわゆる uniq として set も使えますが distinct も有ります。

明らかに \(D(S_{4}) = A_{4}\) なので、ここまでが旧ブログの内容です。

まとめ

3つの記事をまとめたので説明が手抜きになりました。

勉強なので自分で書きましたが permutation のような組み合わせの関数は clojure.math.combinatorics に豊富にあるのでそちらを使うほうがいいかも知れません。

Clojure というと Web 関連で使うことが多いと思いますが、自分としては OpenGL で使いたいのでそれはまたいずれやるつもりです。