自由群の計算(2)

あれやこれやで理由を付けて(要するにサボっていた)群の話を全然進めていなかったが,以前より少しだけHaskellの勉強が進んだので自由群の定義を書きなおしてみた. 今回は Group 型クラスと,その instane としての FreeGroup という事にして書いてみた. ※コードがコンパイルを通ったところで満足したのでテストはこれから.

(Haskell なのにコメントが//で始まっていたりするのはご愛嬌. Wordpress のコード表示が Haskell に対応しておらず,やむなく親戚(?)の Scala だということにしてコード表示方式を設定している.)

//------------------------------------
//-- General Group type class
//------------------------------------
class (Eq a) => Group a where
  unit :: a
  (#) :: a -> a -> a
  inv :: a -> a
  pow :: a -> Int -> a
  x `pow` n  | (n==0)    = unit
             | (n >0)    = foldl1 (#) (replicate n x)
             | otherwise = foldl1 (#) (replicate (-n) x)

//------------------------------------
//-- Element for Free Group
//------------------------------------
type Element s = (s, Int)
antielement :: Element s -> Element s
antielement (x, i) = (x, -i)

//------------------------------------
//-- FreeGroup
//------------------------------------
data FreeGroup s = Word [Element s]

reduce :: (Eq s) => [Element s] -> [Element s]
reduce = foldr  reduce_rec []
  where reduce_rec :: (Eq s) => Element s -> [Element s] -> [Element s]
        reduce_rec t [] = [t]
        reduce_rec t (u:us) = (red2 t u) ++ us
          where red2 :: (Eq s) => Element s -> Element s -> [Element s]
                red2 (s1, i1) (s2, i2)
                  | (s1==s2)&&(i1+i2==0)  = []
                  | (s1==s2)              = [(s1, i1+i2)]
                  | otherwise             = [(s1,i1), (s2, i2)]

instance (Eq s) => Eq (FreeGroup s) where
  (==) (Word xs) (Word ys) = (reduce xs) == (reduce ys)

instance (Eq s) => Group (FreeGroup s) where
  (#) (Word xs) (Word ys) = Word (reduce (xs++ys))
  inv (Word xs) = Word (map antielement (reverse xs))
  unit = (Word [])

foldl と foldr:いつ適用できるか(Haskell初心者)

Haskell初心者記事.Haskellで再帰処理を書くのは簡単だが,再帰は振る舞いを理解するのが難しいこともあり,fold系のパターンで書ける場合はそれらのライブラリ関数(foldl, foldr, foldl1,…など)を使って書くことが推奨されている.それをやるためには,これらのライブラリ関数をしっかり理解しておく必要があるので,とりあえず最も基本的と思われるfoldl や foldr だけでも少し整理してみた.

foldl
foldl の代表的な定義は次のようになる:

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f x [] = x
foldl f x (y:ys) = foldl f x' ys
   where x' = f x y

foldl f という塊が目立つので g = foldl f として書きなおしてみると

g :: a -> [b] -> a
g x [] = x
g x (y:ys) = g x' ys
   where x' = f x y

ただしf :: a -> b -> a

となる.そこで,上のgのようなパターンが出てきたらそれを foldl f と書き直せると理解できる.

foldr
foldr の代表的な定義は次のようになる:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

foldr f z という塊が目立つので h = foldr f z として書きなおしてみると

h :: [a] -> b
h [] = z
h (x:xs) = f x (h xs)

ただし f :: a -> b -> b

となる.そこで,上のhのようなパターンが出てきたらそれを foldr f z と書き直せる事がわかる.

前回の記事から例示
前回の記事で,reduceという関数を再帰で書いていた.上で調べたことを用いて reduce を foldl または foldr で書き直せないか検討してみよう.

元のコードはこれ:

reduce :: (Eq a) => Word a -> Word a
reduce [] = []
reduce (x:xs) = red_rec x (reduce xs)
  where red_rec :: (Eq a) => X a -> Word a -> Word a
        red_rec x [] = [x]
        red_rec x (y:ys) = (red2 x y) ++ ys

ざっと見比べると reduce は h の形に似ている.そこで,reduce = foldr red_rec [] と書けそうに見える.実際それは可能であり

reduce  :: (Eq a) => Word a -> Word a
reduce  = foldr red_rec []
 where red_rec :: (Eq a) => X a -> Word a -> Word a
       red_rec x [] = [x]
       red_rec x (y:ys) = (red2 x y) ++ ys

と書き直せる.

まとめ
何かの処理を再帰で書いてしまってからfold系のライブラリで書きなおすためにはfold系ライブラリ関数を良く理解している必要がある.ライブラリ関数の典型的な実装が与えられている場合,その関数に最初の数個の引数を固定したものを具体的に書きだしてみると,そのライブラリ関数が適用可能な状況がどんな場合か理解しやすくなるかもしれない.この記事ではfoldlとfoldrについてそれらを部分適用した塊の実装を書きだしておき,それを利用して前回の記事に現れた再帰関数をfoldrで書きなおしてみた.

自由群の計算

 離散的な群{G}が与えられているとき,{G}の乗法
{\cdot\colon G \times G \to G}
をカリー化したものを「{\tilde{}}」と書くことにすると
{\tilde{} \colon G \to (G \to G)}
となり,各{g \in G}に対して{G}自身への左作用
{\tilde{g}: G \to G, x \mapsto g\cdot x}
が得られる.このとき,集合{\tilde{G} :=\lbrace \tilde{g} \vert g \in G \rbrace} は写像の合成を積とする半群になり,さらに群{G}の性質を反映して{\tilde{G}}自体も群になる.また,対応{g \mapsto \tilde{g}}{1-1}であることから,{\tilde{G} \hookrightarrow \mathrm{Sym}(|G|)}と見なせることがわかる.({|G|}は群{G}から群の演算を「忘却して」得られた集合).

これによって群{G}に対して集合{|G|}の置換群{\mathrm{Sym}(|G|)}の部分群としての具体的な形を与えたことになる.これは「群の表現」の一種と見なせる.(しかし普通に「群の表現」と言った場合はもう少し違うものを指すことが多い).こうして,離散群{G}がどのようなものであっても,原理的には必ず置換群の部分群として捉える事ができる.

 離散的な群に具体的な形を与えるための別の流儀に「自由群」に基づく方法がある.ルービックキューブのような群論的パズルにおいては,有限個の基本操作の組み合わせによって全ての可能な面の配置が生成される.このように,いくつかの生成元によって生成される群を捉えるための基礎となる枠組みとして考案されたのが自由群である.

 自由群の考え方は非常に簡単である.生成元に対応する文字の集合{X :=\lbrace x_1, ..., x_n\rbrace}に対して{\tilde{X} := \lbrace (x, \epsilon) \vert x \in X, \epsilon\in \lbrace 1, -1 \rbrace\enskip\rbrace}の元からなる有限リストを{X}のワードと呼ぶ.{X}のワードの集合を{\mathrm{Word}(X)}と書く.したがって{\mathrm{Word}(X):=\mathrm{List}(\tilde{X})}.以下ではリストをHaskell寄りの表記で扱う.したがって{ \,[a_1,...,a_n] \in \mathrm{Word}(X)},等.また,空リストもHaskellに倣って{[]}で表すことにする.
 ワード{w}が被約(reduced)であるとは,{w = [a_1, ..., a_n]}の要素の中に{(s, 1) (s, -1)}{(s, -1) (s, 1)}のようなタイプの隣接が出現しないことである.いかなるワードも,左からあるいは右から順に隣接する要素を見比べて{(s, 1) (s, -1)}{(s, -1) (s, 1)}のタイプのペアをリストから除去することによって被約なワードへと還元(reduce)できる.

 二つのワード{w_1, w_2}は,それらを還元して得られたワードが同じであるとき,すなわち{\mathrm{reduce}(w_1) = \mathrm{reduce}(w_2)}であるときに同値であると定義する.この同値関係によって{\mathrm{Word}(X)}を類別して得られた集合を{\mathrm{Free(X)}}で表すことにする.

 よく知られているように,任意の集合{\Omega}に対して{\mathrm{List}(\Omega)}は連接演算{\odot}(Haskellでは{+\!+})を「積」とする半群になる:
{[a_1, ..., a_n] \odot [b_1, ..., b_m] = [a_1, ..., a_n, b_1, ..., b_m]}.
この半群としての積を{\mathrm{Free}(X)}にも導入する.

 ワード{w=[(x_1,\epsilon_1), (x_2, \epsilon_2), ..., (x_n, \epsilon_n)]}の逆ワード{w^{-1}}を次のように定義する:
{w^{-1} := [(x_n, -\epsilon_n), ..., (x_2, -\epsilon_2), (x_1, -\epsilon_1)].}

 容易に確かめられるように,任意のワード{w}に対して
{\mathrm{reduce}(w \odot w^{-1}) = \mathrm{reduce}(w^{-1}\odot w) = [].}
{\mathrm{Free}(X)}の立場から見れば,これは全てのワードが積{\odot}に関する逆元を持つ事になる.

 以上の定義により,{\mathrm{Free}(X)}{[]}を単位元とする積{\odot}を持つ群になる.{w \in \mathrm{Free}(X)}の逆元は{w^{-1}}(の、{\mathrm{reduce}}による同値類)で与えられる.

 以上の内容は,話としてはさほど難しくないが,上の説明でも事情を完全に明確には記述できていない.明確に記述するための有効な方法の一つはそれを実行する計算機のコードを書くことである.群論の本の自由群の箇所を読んでいて自分がすべての基本概念を明確に理解している事についての疑問が生じたので,自由群の計算をするためのコードをHaskellで書いてみた.(慣れているC++を使わずにHaskellで書いたのは練習のためもあるが,Haskellのコードの方が可読性を高く保てるのではないかと思ったからでもある.)

 コードの簡単な説明:{\tilde{X}}に相当するのが data X だが,上の説明とは少し違って{(x, i)}という形式では{i=1 \text{or} -1}と限定されているわけではない. この形式に基づけば{[(x,1), (x,1), (x,1)]}{[(x,3)]}と簡約されることになるが,本質においては伝統的な自由群の扱いと変わる事はない.
isReduced はワードが被約であるかどうかを判定する関数である. reduce2は二つの{\tilde{X}}の元{(p, i)}{(q,j)}に対し,ワード{[(p,i), (q,j)]}を簡約した結果を返す. ワード簡約の関数reduce は最終的にはreduce2 を呼び出す事で処理を行う. 自由群の積としては記号#を用いた. 関数antiword は与えられたワードの逆ワード(積の逆元)を返す関数である. ワードの「べき乗」を計算する関数powもついでに書いてみた.

 これらのコードはそれ自体として有用ではないかもしれないが,このコードを書く経験を通して,自由群の定義の理解を深める事が出来たと感じている.

--文字の集合X
data X a = X a Int deriving(Eq, Ord, Show)
type Word a = [X a]

isReduced :: (Eq a) => Word a -> Bool
isReduced xs = all isReduced2 (pairs xs)
  where isReduced2 :: (Eq a) => (X a, X a)-> Bool
        isReduced2 ((X p _), (X q _))
           | (p == q) = False
           | otherwise = True

        pairs :: [X a] -> [(X a, X a)]
        pairs [] = []
        pairs [_] = []
        pairs (x:y:zs) = (x,y) : pairs (y:zs)

red2 :: (Eq a) => X a -> X a -> Word a
red2 (X p i) (X q j)
    | (p==q)&&(i+j==0) = []
    | (p==q) = [(X p (i+j))]
    | otherwise = [(X p i), (X q j)]

reduce :: (Eq a) => Word a -> Word a
reduce [] = []
reduce (x:xs) = red_rec x (reduce xs)
  where red_rec :: (Eq a) => X a -> Word a -> Word a
        red_rec x [] = [x]
        red_rec x (y:ys) = (red2 x y) ++ ys

-- Product of the free group
(#) :: (Eq a) => Word a -> Word a -> Word a
xs # ys = reduce (xs ++ ys)

antiword :: Word a -> Word a
antiword xs = map antichar (reverse xs)
  where antichar :: X a -> X a
        antichar (X p i) = X p (-i)

pow :: (Eq a) => Word a -> Int -> Word a
pow w n
  | (n == 0) = []
  | (n > 0) = foldl1 (#) (replicate n w)
  | otherwise = foldl1 (#) (replicate (-n) aw)
    where aw = antiword w

追記(2012/09/11): 一箇所内容を修正しました。また、パソコンで見ると数式文字が灰色で見づらいので修正してみました。