Core Simplifier
しつこく、Simplifier。
どうでもいい使い方その1。RULESで値を定義する
{-# OPTIONS -fglasgow-exts #-}
{-# NOINLINE hoge #-} -- これがないと勝手にINLINE展開されるので注意
{-# RULES "hoge" hoge = "hello,Bob" #-} -- 本当の定義
hoge = hoge -- dummy definition
main = print $ (hoge::String) Simplifyは型チェックの後にやるっぽいので、型チェックすり抜けたら、面白いと思ったけど、無理だった。使い道はなさげ。
どうでもいい使い方その2。Simplifierを使って、compile-time programming
{-# OPTIONS -fglasgow-exts #-}
{-# RULES "append/nil" forall x . (++) [] x = x #-}
{-# RULES "append/cons" forall a x y. (++) (a:x) y = a:(x ++ y) #-}
main = print $ [1,2,3]++[4,5,6]項書換え系なので、多分Turing-complete。compile-time programmingというと、Template Haskellとか思い出しますが、そこらへんは知らないので。まあ、なんかに使えるかもしれない
Haskellに限らないだろうけど、効率のよいコードを書こうとすると、非直感的なコードになったりしがちだと思うんで、そのへん直にコードを書くんじゃなくて、コード部分は分かりやすくナイーブに書いて、RULESをうまく定義して、効率的なコードに変換できるとよいなーということを思う。というような文章をダラダラ書かず、例をあげれればいいんだけど、Haskellで効率的なコードを書いた経験が浅いので(というか、Haskellの経験が浅いので)、なんのイメージもわかないのだった。HaskellチューニングTipsみたいなん、どっかねーかなー(そんな、HowTo本を求める現代の若者的発想はよくない。いや、現代の若者なので仕方ない)。まあ、RULESで出来るのは、contextを無視した局所的な変換だけなので、微妙かもしれんけど。
maximum segment sum(mss)というのが、アルゴリズムの導出という文脈でよく出てくる。
Clalculating Functional Programs。
mssというのは、整数列(実数でも、あるいは全順序と足し算さえ定義されてれば何でもいいですが)を与えて、総和が最大となる部分列を探して、その総和を求める問題。[1,-2,4,1,2,-5,8,-4,1]だったら、[4,1,2,-5,8]がそのような部分列で、総和は10。ナイーブに考えると、全ての部分列のリストを作って、総和を計算して、最大値を取ればいい。これは、リスト長の3乗のオーダーの計算時間がかかる。さて、GHCの最適化は、こいつを線形時間のアルゴリズムに変形できるでしょうか！?
ナイーブなアルゴリズム。
--maximum = foldr max (-1/0) --concat = foldr (++) [] --sum = foldr (+) 0 --scanr f e = foldr (\a bs -> f a (head bs):bs) [e] inits = foldr (\a xs -> [] : (map (a:) xs)) [[]] tails = foldr (\a xs -> (a : head xs):xs) [[]] mss = maximum . map sum . concat . map inits . tails
で、これが、
mss2 = maximum . scanr (\a b -> (max 0 (a+b))) 0 mss3 = maximum . foldr (\a bs -> (max 0 (a+head(bs))):bs) [0] --scanr展開しただけ
とコンパイルした時に同等となるように融合変換できるとよいのだけど、組み込みの関数及びRULESは余り使えない。
一応関係ありそうなとこを引いておく。
maximum :: (Ord a) => [a] -> a
maximum [] = errorEmptyList "maximum"
maximum xs = foldl1 max xs
---------------------------------------
concat :: [[a]] -> [a]
concat = foldr (++) []
{-# RULES
"concat" forall xs. concat xs = build (\c n -> foldr (\x y -> foldr c y x) n xs)
-- We don't bother to turn non-fusible applications of concat back into concat
#-}
-----------------------------------------
scanr :: (a -> b -> b) -> b -> [a] -> [b]
scanr _ q0 [] = [q0]
scanr f q0 (x:xs) = f x q : qs
where qs@(q:_) = scanr f q0 xs
------------------------------------------
-- List sum and product
{-# SPECIALISE sum :: [Int] -> Int #-}
{-# SPECIALISE sum :: [Integer] -> Integer #-}
{-# SPECIALISE product :: [Int] -> Int #-}
{-# SPECIALISE product :: [Integer] -> Integer #-}
-- | The 'sum' function computes the sum of a finite list of numbers.
sum :: (Num a) => [a] -> a
-- | The 'product' function computes the product of a finite list of numbers.
product :: (Num a) => [a] -> a
#ifdef USE_REPORT_PRELUDE
sum = foldl (+) 0
product = foldl (*) 1
#else
sum l = sum' l 0
where
sum' [] a = a
sum' (x:xs) a = sum' xs (a+x)
product l = prod l 1
where
prod [] a = a
prod (x:xs) a = prod xs (a*x)
#endifまあ、maximumとかは仕方ない気もする。
{-# OPTIONS -fglasgow-exts #-}
{-# RULES "sum" sum = foldr (+) 0 #-}
{-# RULES "scanr" forall f e . scanr f e = foldr (\a bs -> f a (head bs):bs) [e] #-}
{-# INLINE maxs #-}
{-# INLINE inits #-} --念のため
{-# INLINE tails #-} --念のため
inits :: [a] -> [[a]]
inits = foldr (\a xs -> [] : (map (a:) xs)) [[]]
tails :: [a] -> [[a]]
tails = foldr (\a xs -> (a : head xs):xs) [[]]
maxs = foldr max (-1/0)
mss = maxs . map sum . concat . map inits . tails
mss2 = maxs . scanr (\a b -> max 0 (a+b)) 0
ls = [1,-2,4,1,2,-5,8,-4,1]
main = print $ (mss ls , mss2 ls)とかやって試したけど、てんでダメでした！maxsとか使ってるのは、(-1/0)が整数じゃないとこから来る大人の事情。
結論：GHCのsimplifierもたいしたことない
というか、GHCのライブラリって全体的に、融合変換かけやすい構造になってないような。まあ、GHC黎明期には、RULESによる最適化みたいなんがなくて、後から追加されたとかいう歴史的事情かもしれないけど。所詮、単なる項書換え系なので、自分でうまくルールを追加して、綺麗に最適化がかかるようにできるとは思うけど、明らかに、効率のよいコードを直に書いたほうが速いよな〜。私の頭が悪いので、ついていけないというのも多分にあると思うが。あとやっぱ完備化とかちゃんと考えないといかんかね
