トップ «前の日記(2005-12-12) 最新 次の日記(2005-12-15)» 月表示 編集

日々の流転


2005-12-14 [長年日記]

λ. Monadと思ったけどMonadじゃなかった何か

以下がMonadになってると思って頑張って証明しようとした*1けど、結局Monadになっていないことが分かってショボーン(´・ω・`)。もし(++)が可換であればMonadになるんだけどね*2

-- coinductive
data Automata i o = Automata [o] (i -> Automata o)

instance Monad (Automata i) where
    return x = Automata [x] (\_ -> mzero)
    (Automata as t) >>= g =
        msum [g a | a <- as] `mplus` Automata [] (\c -> t c >>= g)

instance MonadPlus (Automata i) where
    mzero = Automata [] (\_ -> mzero)
    Automata xs t `mplus` Automata ys u =
        Automata (xs++ys) (\c -> t c `mplus` u c)
Tags: haskell

*1 ちなみに、こういうのを証明するのには guarded coinduction を使うと楽で良い

*2 もし仮にHaskellにBagやSetがあるなら、そいつでリストを置き換えればMonadになる。