Codensityモナド
gpt-5.icon
Codensityモナドは、Freeモナドや リストモナド などの「非効率なモナド」を効率化するために使われる抽象的なモナドです。主に 左結合的な >>= による遅延評価の非効率性を改善 するために登場しました。 🔹 基本の動機：モナド結合の非効率性
code:haskell
m1 >>= \x ->
m2 >>= \y ->
m3 >>= \z ->
return (x + y + z)
ところが、例えば Free モナドや List モナドのように「構造を再構築」するようなモナドでは、左結合的に >>= を評価していくと効率が悪くなります。
Free モナドでは巨大な中間構造（ASTのようなもの）ができる
List モナドでは巨大なリストの連結 (++) が大量に起きる
このような 左結合的モナド結合のコストを避けたい、というのが Codensity の出発点です。
🔹 定義
code:haskell
newtype Codensity m a = Codensity { runCodensity :: forall r. (a -> m r) -> m r }
ここでの forall r. (a -> m r) -> m r は CPS（継続渡し形式: Continuation Passing Style） です。 Codensity m a は「m を CPS変換したもの」と思ってよいです。 🔹 直感的な理解
通常のモナド m a は「a を包んだ構造」です。
一方で Codensity m a は「a に対して後続処理 (a -> m r) を与えると m r を返す関数」です。
つまり「a を包むのではなく、a に続く処理を受け取る形」になっています。
🔹 モナドインスタンス
Codensity 自身もモナドです：
code:haskell
instance Monad (Codensity m) where
return x = Codensity ($ x)
Codensity m >>= f = Codensity $ \k ->
m (\a -> runCodensity (f a) k)
この定義をみると、>>= が 関数合成のように右結合で展開される ことがわかります。
この右結合化こそがパフォーマンス向上の鍵です。
🔹 効果：左結合を右結合に変える
例えば、リストモナドで bind が左結合になると、++ のコストが線形に増えていきます。
code:haskell
(xs >>= f) >>= g
は concatMap g (concatMap f xs) となり、中間リストが何度も構築されます。
これを Codensity を使って書き換えると：
code:haskell
toCodensity :: Monad m => m a -> Codensity m a
toCodensity m = Codensity (m >>=)
fromCodensity :: Monad m => Codensity m a -> m a
fromCodensity (Codensity k) = k return
として、Codensity を通すと次のようになります：
code:haskell
fromCodensity (toCodensity xs >>= f >>= g)
このとき内部では右結合的に合成され、中間リストが作られなくなります。
🔹 具体例：リストモナドの高速化
code:haskell
slowList = do
return (x + y)
fastList = fromCodensity $ do
return (x + y)
slowList は二重ループで巨大な中間リストを作りますが、
fastList は Codensity による CPS 化で中間リスト構築を回避し、劇的に高速化します。
🔹 Free モナドとの関係
Free モナドも Codensity を通すと高速化できます。
code:haskell
foldFree :: Monad m => (f a -> m a) -> Free f a -> m a
foldFree interpret = fromCodensity . go
where
go (Pure a) = return a
go (Free f) = liftCodensity (interpret (fmap go f))
Free モナドのインタープリタ (foldFree) が遅い場合でも、
Codensity 経由にすることで 右結合化によって再帰のオーバーヘッドを避けられる ため、数十倍高速になることもあります。
🔹 関連キーワード
Yoneda lemma
Codensity は実は米田埋め込み の一形態でもあります。