haskellの差分リストが地味にエレガントな件

差分リスト

やはり基本が大事ということで、久しぶりに「すごいH本」を読み直していたところ、差分リストに遭遇、ダラダラと読んでいましたが...

「これって地味に凄くねぇ？、ここまで考えて普段、コーディングしたことぇーだろ」

 って感じになってしまって、ついブログをかいてしました。 「すごいH本」ではWriterモナドのログの蓄積方法について、アルゴリズムによっては効率が悪い処理になってしまうよという説明からの、もうクリスがいっちゃうと

* 効率的なリストの結合方法 

n1 ++ (n2 ++ (n3 ++ (n4 ++ (n5 ++ f)))) ・・・右結合

と

* 非効率なリストの左結合方法

((((n1 ++ n2) ++ n3) ++ n4) ++ n5) ++ f　・・・左結合

細かいことはいいとして、左結合のリストの場合、右側を結合する度に、左側を最初から計算する必要があるため、結合処理が多い場合非効率なコードになってしまうということで、そこで差分リスト

パクる

まず、DiffListの定義、

newtype DiffList a = DiffList { getDiffList :: [a] -> [a] }

DiffListはa型の配列をとってa型の配列を返す関数と定義する

それから、リストからDiffListへの変換関数

toDiffList :: [a] -> DiffList a
toDiffList xs = DiffList (xs++)

それの逆、パターンマッチさせた関数fに[]を食わせてリストに変換する

fromDiffList :: DiffList a -> [a]
fromDiffList (DiffList f) = f []

そしてMonoidクラスのインスタンスへ設定する

import Data.Monoid
instance Monoid (DiffList a) where
    mempty = DiffList (\xs -> [] ++ xs)
    (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))

memptyは単位元の宣言で、かっこいいのはmappend、例えば

f = \xs -> "最近" ++ xs
g = \ys -> "結婚して" ++ ys

で

f `mappend` g ってすると、\xs -> "最近" ++ ("結婚して" ++ xs)

となるので、これがDiffList (\xs -> f (g xs))になる

算数的に書くと

f(x) = A ++ x
g(y) = B ++ y

f(x) `mappend` g(y) = f(g(y)) = A ++ (B ++ y)

まさに右結合じゃないですか！、、、なんと綺麗な！

使ってみる

*Main> let d1 = toDiffList "最近"
*Main> let d2 = toDiffList "結婚して"
*Main> let d3 = toDiffList "皆からやな奴って言われるようになりました"
*Main> let f = d1 `mappend` d2 `mappend` d3
*Main> putStrLn $ (getDiffList f) []
最近結婚して皆からやな奴って言われるようになりました
*Main> putStrLn $ fromDiffList f
最近結婚して皆からやな奴って言われるようになりました
*Main>

奴は、最近調子に乗ってます

そしてmemptyは

*Main> putStrLn $ fromDiffList $ d3 `mappend` mempty
皆からやな奴って言われるようになりました
*Main> putStrLn $ fromDiffList $ mempty `mappend` d3
皆からやな奴って言われるようになりました 

Monoidしてるね、なるほど、素晴らしい

mappendでDiffListをつなげていって最後に[]で全部をつなげるところなんか

「すげぇー」

って思わない？、haskellっていい