trifle

技術メモ

Stateモナドでランレングス圧縮

最近Stateモナドを学び始めた. 状態を保持しながら計算を進めたいときに便利のようである.
とりあえず,

  1. get で状態を取り出し, put で状態を更新し, 最後に return で最終的な値を出すStateモナドを定義(Stateモナドの型は State [保持する状態の型] [最終的な値の型]
  2. 初期状態を設定し, evalState で最終的な値を取り出す

というのが分かれば実用的にはよさそう. まあもう少し色々なバリエーションの関数が用意されていると思うが...
ネットの記事で分かりやすかったのは公式のチュートリアル

と以下の記事.



ということで試しに使ってみる.
そういえば, 大学の課題でランレングス圧縮(連長圧縮)のプログラムを書かされた. これは例えば AAAATTCCCCTGGA4T2C4T1G2 と表現する.
前から1文字ずつ読む中で, (途中まで読んで圧縮した文字列, 前回読んだ文字, その文字を読んだ回数)の3つを状態として保持するので, Stateモナドを使えばうまく出来る気がして, やってみたら, たぶん出来た.

RunLengthEncoding.hs

module Main(main) where

import Control.Monad.State

type EncodingString = String
type EncodedString = String
type LastChar = Char
type LastNum = Int

rle :: String -> State (EncodingString, LastChar, LastNum) EncodedString
rle (x:xs) = do
    (s, c, i) <- get
    case x of n | n == c        -> put (s, c, i + 1)
                | otherwise     -> put (s ++ [c] ++ show(i), x, 1)
    rle xs

rle [] = do
    (s, c, i) <- get
    return (s ++ [c] ++ show(i))

main :: IO ()
main = do
    str <- getLine
    let headChar = head str
    putStrLn $ evalState (rle str) ([], headChar, 0)
$ stack runghc RunLengthEncoding.hs
AAAATTCCCCTGG  -- 入力
A4T2C4T1G2  -- 出力

他言語で書くときに比べて, 保持する状態が見やすくて良いと思うのですが, いかがでしょう.