Haskell::GR-nの生成(その5)

最近、Haskellのコードを書き散らかして多少なりとも勘所が見えてきたのか、ちょっと前に書いたコードの不恰好な所が目に付く様になってきた。

で、今の知識でGR-nを生成するコードを書き下してみる。

-- gr5.hs
import System
import List
main :: IO ()
main = do { args <- getArgs
; let [n, m] = if length args == 2 then map read args else [4,20]
; putStrLn $ unwords $ map show $ take m $ gr n
}
gr :: Int -> [[Int]]
gr n
| n<1         = []
| n==1        = [[0]]
| n==2        = [[0, x] | x<-[1..]]
| otherwise   = scanline 1
where
grs = gr $ n - 1
lm = n * (n - 1) `div` 2
scanline :: Int -> [[Int]]
scanline m = let {
; zs = filter gr_p $ zip [lm..(lm + m -1)] $ reverse $ take m grs
} in [ys ++ [x] | (x, ys)<-zs] ++ (scanline $ m + 1)
where
gr_p :: (Int, [Int]) -> Bool
gr_p (x, ys)
| x <= last ys        = False
| otherwise           = null $ intersect [x-y|y<-ys] $ diff_set ys
diff_set :: [Int] -> [Int]
diff_set []     = []
diff_set (x:xs)
| null xs     = []
| otherwise   = [x'-x|x'<-xs] ++ diff_set xs
--

書き直すに当たって、

  • リスト処理をもっと工夫できないか見直す(標準プレリュードの関数をある程度把握できれば、無駄なコードを省けるようになってくる)
  • !!演算子(リストのインデックスアクセス)に頼らない
  • map式をlist comprehensionで書き直せないか検討する(単純なmap式なら書き直したほうが見やすい場合が結構ある。ただし、$でつながれた式などの途中のmapを書き換えると逆に意味が取りにくくなることもあるので無闇に書き換えない)
  • 無駄な引数渡しをしてないかチェック
  • パターンマッチング(x:xsなど)の活用

などに注意してみた。これは、Haskellに限らずLispなどの処理系でも当てはまる点は多いと思う。

ちなみに、書き直したコードでGR-40の一つ目を計算するのにかかる時間を測定すると、

% time ./gr5 40 1
[0,1,3,8,12,22,28,46,59,82,99,114,149,175,214,244,292,333,396,453,497,561,623,732,765,817,961,990,1084,1263,1346,1481,1561,1689,1762,1884,2124,2190,2274,2379]
517.714u 0.278s 8:39.96 99.6%   654+877k 0+0io 0pf+0w

と多少高速化できた。やはり無駄なことをやっていた所がそれなりにあったということなのだろう。