トップ «前の日記(2005-10-31) 最新 次の日記(2005-11-02)» 月表示 編集

日々の流転


2005-11-01 [長年日記]

λ. Wang's Algorithm

ふと、Wang's Algorithm (ワンのアルゴリズム) を素朴に書いてみた。 が、イマイチ。

import Control.Monad (guard,msum)
import Data.List (intersect)
import Data.Maybe (isJust, listToMaybe)

data Formula x
    = Atom x
    | Not   !(Formula x)
    | Imply !(Formula x) !(Formula x)
    | And   !(Formula x) !(Formula x)
    | Or    !(Formula x) !(Formula x)
    deriving Eq

type Sequent x = ([Formula x], [Formula x])

isValid :: Eq x => Sequent x -> Bool
isValid = isJust . isValid'

isValid' :: Eq x => Sequent x -> Maybe ()
isValid' (l,r) =
    do xs <- listToMaybe $ msum $
         [ do let i = intersect l r
              guard $ not $ null i
              return []
         , do (Not p, r) <- pick r
              return [(p:l,r)]
         , do (Not p, l) <- pick l
              return [(l,p:r)]
         , do (Imply p q, r) <- pick r
              return [(p:l,q:r)]
         , do (Or p q, r) <- pick r
              return [(l,p:q:r)]
         , do (And p q, l) <- pick l
              return [(p:q:l,r)]
         , do (Or p q, l)  <- pick l
              return [(p:l,r), (q:l,r)]
         , do (And p q, r) <- pick r
              return [(l,p:r), (l,q:r)]
         , do (Imply p q, l) <- pick l
              return [(q:l,r), (l,p:r)]
         ]
       mapM_ isValid' xs
       return ()

pick :: [x] -> [(x,[x])]
pick []     = []
pick (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- pick xs]
Tags: haskell

λ. 『株取引のことがマンガで3時間でマスターできる本』, 木村 佳子

を読んだ。あまり期待してなかったけど、結構良くまとまっていて、基礎知識を得るにはちょうど良かった。

株取引のことがマンガで3時間でマスターできる本 (アスカビジネス)(木村 佳子)

Tags:

λ. SML#

Zeta版って……(笑