日々の流転

λ. 第八回圏論勉強会

今日は圏論勉強会でした。

写真。

λ. 『月光魔術団1　春の魔法使い』, 平井 和正

古本屋で見かけて、中学生のころ雑誌で紹介されていたのを思い出したので、読んでみた。犬神メイというキャラクタは多少面白いかもしれないが、文章のレベルが低すぎるな。

λ. 無記名投票での投票CO

人狼審問: (604)乾いた村の2日目に無記名投票での投票COの話が出ていた。メモ。

語り部 デボラ / (76)2005/06/23 13:07:05

>>67
「無記名投票CO」について考えてみた。

・投票が複数あって、CO者の数が足りなかった場合、能力者が襲撃されたと考える事ができる。

しかし、後から「遅れて済まない、実はあと１人のCO者は俺だ」と出て来る事も十分考えられる（当然、その場合、彼は信用を勝ち取る努力をしなければならないが）。

また、複数投票があって（内訳が真によるもの１、人狼による１だったとする）後で真のみが名乗り出た場合、真は無用な疑いを被る事になる…。

λ. Backtracking, Interleaving, and Terminating Monad Transformers (Functional Pearl). Oleg Kiselyov, Chung-chieh Shan and Daniel P. Friedman and Amr Sabry

LtUより。

• 論文中のコード
• monad が strict だというのはどう定義されるのだろう?
  • (2005-09-04 追記) 「runST (undefined >> return ())」 は Control.Monad.ST.Strict ではundefinedに、Control.Monad.ST.Lazy では()になるけど、これは関係ある?
• 「List as transformer can only be applied to commutative monads.」がちょっと良く分からない。
  • (2005-09-07 追記) 単に「可換なモナドに適用した場合しかmsplitはちゃんと定義出来ない」ってことか。
• Prolog の cut は知ってるけど soft-cut なんてのもあったのか。
  • (2005-11-01 追記) 「A *-> B ; C」か。そういえばそんなのもあったな。

(2005-09-30 追記) msplitは兎も角、interleaveやbindiはプリミティブとしてはイマイチ。例えば、「interleave a (interleave b c)」ではa,b,cは均等には実行されない。n個の計算を均等に実行するには結局msplitを使って別の関数を定義せざるを得ない。bindiもinterleaveの欠点を受け継いでいて、第一引数と第二引数の計算は均等には実行されない。……といって、どうすればいいかは良く分からんけど。

とりあえず、自分でもコンビネータをちょっと書いてみた。interleaveNはn個の計算を均等に実行するための関数、bindzは第一引数と第二引数の計算が均等(?)に実行されるbind。bindzは自然数の直積と自然数との全単射を作るときなんかに良くやるように、ジグザグに動く。

interleaveN :: LogicM m => [m a] -> m a
interleaveN [] = mzero
interleaveN ms = msplitL ms interleaveN
 
bindz :: LogicM m => m a -> (a -> m b) -> m b
bindz m f = loop m []
    where loop m xs =
            do r <- msplit m
               case r of
                Nothing -> interleaveN xs
                Just (a,m') ->
                    msplitL (f a : xs) (loop m')
 
msplitL :: LogicM m => [m a] -> ([m a] -> m a) -> m a
msplitL [] k = k []
msplitL (m:ms) k =
    do r <- msplit m
       case r of
         Nothing -> msplitL ms k
         Just (a, m') ->
             return a `mplus` msplitL ms (k . (m':))