多引数flipをポイントフリースタイルで書く
http://www.tom.sfc.keio.ac.jp/~sakai/d/?date=20061220#p02
経由で
http://haskell.g.hatena.ne.jp/jmk/20061220/1166594317
と、あと
http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tdiary/?date=20041210
が動機。
方針:n-引数flipは、一般にn!個のバリエーションがあって、全部やるのはしんどいので、対称群は単純置換で生成されるという事実から、単純置換だけやることにする(単純置換というのは、(1, .. ,n)のi番目とi+1番目を入れ替えるような置換)。単純置換の積は、単純に関数合成で書けるので、単純置換さえポイントフリーで書いておけば、(少なくとも原理的には)任意のn-引数flipがポイントフリーで書ける。
(追記)単純置換のことを互換と書いてたorz互換とは、i番目とj番目のみを入れ替え、他は固定するような置換。i番目とi+1番目を入れ替えるような置換は単純置換(あるいは単純互換)とか呼ぶらしい(あまり聞かない用語だけど。適当に探して見ると、「隣り合う互換」とか書いてたりするなぁ)。単純置換は勿論互換。任意の置換は、互いに素な巡回置換の積として表すことができる。巡回置換は更に互換の積として表すことができる。最後に、任意の互換は、単純互換の積で書くことができる。従って、任意の置換は単純互換の積で書くことが出来る。対称群が単純置換で生成されるという事実は、しばしば、あみだくじで説明される
約束:n-引数flipで、1+(i mod n)番目と1+(i+1 mod n)番目の要素を入れ替えるものをperm(i,n)として、i = j (mod n)の時、perm(i,n) = perm(j,n)とする。
まず、
・perm(0,2)とperm(1,2)は、普通のflipとなる ・i<n-1に対して、perm(i,n) = perm(i,n+1) ・特に、perm(0,n) = flip(n>2)
が成り立つので、n>2に対して、perm(n-1,n)とperm(n-2,n)が書ければよい。
perm(n-2,n)は色々試してると、n>1に対して、
perm(n-1,n+1) = (perm(n-2,n).)
から帰納的に求まることに気付く。少し例
perm(1,3) = (perm(0,2).) = (flip.) perm(2,4) = (perm(1,3).) = ((flip.).) perm(3,5) = (perm(2,4).) = (((flip.).).)
めがっさシンプル。証明は簡単にできるんでないかな
perm(n-1,n)は、とりあえず、一つ左にずらす置換circ(n)を導入する。つまり、circ(n)(1, .. ,n) = (2, .. , n,1)となる。circ(n)は
circ(2) = flip
circ(n) = (perm(n-3,n-1).).circ(n-1) (n>2)
で帰納的に定義できる一方、
circ(n) = perm(n-1,n). .. . perm(1,n)
とも書ける。perm(i,n).perm(i,n)=idに注意して、
perm(n-1,n) = circ(n).perm(1,n). .. . perm(n-2,n) (n>2)
を得る。なんかシンプルでないが、計算例
perm(2,3) = circ(3) . perm(1,3) = (flip.) . flip . (flip.) perm(3,4) = circ(4) . perm(1,4) . perm(2,4) = = ((flip.).) . (flip.) . flip . (flip.) . ((flip.).) perm(4,5) = circ(5) . perm(1,5) . perm(2,5) . perm(3,5) = (((flip.).).) . ((flip.).) . (flip.) . flip . (flip.) . ((flip.).) . (((flip.).).)
を見ると、
perm(n-1,n) = perm(n-2,n) . perm(n-2,n-1) . perm(n-2,n)
が成り立ってるっぽい。めがっさ綺麗じゃん！これも証明は楽にできるっぽいが、後日気が向いたら。まとめると、
perm(0,2) = perm(1,2) = flip perm(n-2,n) = (perm(n-3,n-1).) (n>2) perm(n-1,n) = perm(n-2,n) . perm(n-2,n-1) . perm(n-2,n) (n>2) perm(i,n) = perm(i,n-1) (i<n-2 , n>3)
を得た。合ってんのかな･･･
んで、最後に、これをTemplate Haskell使って書く。Template Haskellは使ったことなかったけど、
http://www.kmonos.net/wlog/29.php#_0103030717
http://d.hatena.ne.jp/tanakh/20041227
http://haskell.org/haskellwiki/Template_Haskell
あたりを参考に。
{-# OPTIONS -fth #-}
module Perm where
import Language.Haskell.TH
flipN :: Int -> Int -> ExpQ
flipN i n | n==2 = [| flip |]
| i==0 = [| flip |]
| (i<0 || i>=n) = [| $(flipN (mod i n) n) |]
| (n<2) = [| id |]
| (i==n-2) = [| ($(flipN (n-3) (n-1)).) |]
| (i==n-1) =
[| $(flipN (n-2) n) . $(flipN (n-2) (n-1)) . $(flipN (n-2) n) |]
| otherwise = [| $(flipN i (n-1)) |]n<2の時は、恒等射を返すようになってる。んでもって、てすつ
{-# OPTIONS -fth #-}
-- to compile, "ghc --make main.hs -o main.exe"
module Main where
import Perm (flipN)
hnya = $(flipN 2 4) (,,,) 1 2 3 4
main = putStrLn (show hnya) --(1,2,4,3)になるはずやったーゴール！
結論:ポイントフリースタイルで書くと、Template Haskellで書くときに楽
というのは嘘で、perm(i,n)の帰納的定義を書くのに1時間以上かかってるので、普通に書いた方が速い。あと、上の定義を見た瞬間に、ああN引数flipね、とか分かる人は狂ってると思う。
個人的に、compile-time programmingって、あんまし好きじゃないんだけど、融合変換した後のコードをExpQで吐いてもいいのかもしれんと思った。が、最大の問題は、融合変換するとき、ライブラリで定義されてる関数の定義を取れないとまずいんだけど、それを簡単にやる方法がないことだと気付いた今日この頃。
しかし、構文木いじるような操作って、大体、名前の衝突を避ける方法が必要になる気がするけど、gensymみたいなんはないっぽいし、どうするんだろう
