ブロックソートをHaskellで書いてみた
Suffix Arrayを構築するプログラムが非常に簡単に書けるので、ブロックソートも簡単に書けるのではないかと思い、やってみた。
計算量とメモリの空間効率は一切考えない。
import Data.List (sort, tails, inits, group, findIndex, sortBy) main :: IO () main = print $ decode $ encode "cacao" decode :: Ord a => (Int, [a]) -> [a] decode (i,s) = map (\n -> s !! n) ns where suffix = map snd $ sortBy comp $ zip s [0..] comp (x,_) (y,_) = compare x y ns = take (length s) $ iterate (\n -> suffix !! n) $ suffix !! (i-1) encode :: Ord a => [a] -> (Int, [a]) encode s = (i+1, map (last . head) tmp) where tmp = group $ sort $ zipWith (++) (tails s) (inits s) Just i = findIndex (\ss -> 2 == length ss) tmp
うーん。書く人がだめだと、できるコードもだめだな。
以下、書いてて思ったことを列挙(今度、暇な時に考える)
- コンパイルの際にWallオプションをつけても、コードの最終行にあるJust iの部分に警告がでなかった。Nothingの場合は考慮しなくてもいいのだろうか。
- comp (x,_) (y,_)のような、ソートしたいデータとソートの順序を評価する要素が違う場合が個人的によくある。comp (x,_) (y,_)のような関数を定義しない書き方はないだろうか
- findIndexには、lengthに対するgenericLengthというような関数はないのだろうか
- IntとInteger、それにIntegralの使い分けが気になる。なるべく抽象化するべきという考えなので、Integralにしようと心がけている。でも、genericなんちゃらがData.Listをimportしないと使えなかったり、findIndexに対応する関数が見つからなかったりとか、なかなか面倒。なんで、当分の間は常にIntを使うことにしようかな...。