ブロックソートを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を使うことにしようかな...。

or1ko's diary

日々を書きます

ブロックソートをHaskellで書いてみた