具体的に何が不満かっていうと、データファイルを自分で作る方法が分からない上に、元々入っているデータが少な過ぎる。.hoo ファイルがそれっぽいけど、当然作るツールはあるんだと思うし、これはどうすればいいのかなぁ。
cabal で入れるついでに hoogle にも登録される! くらいできたらとても嬉しいんですが、できないかなー。
とりあえず簡単な物から書いてみよう! という事で ST モナド入門を兼ねて書いてみました。
{-# LANGUAGE FlexibleContexts #-} module Stsolver where import Data.List import qualified Data.Traversable as T import Data.STRef import Control.Arrow import Control.Applicative import Control.Monad.State.Lazy import Control.Monad.ST data Problem sol ref = Problem { prfunc :: ([[sol]] -> [sol]), prrefs :: [ref (Problem sol ref)], prrevrefs :: [ref (Problem sol ref)], prsols :: [sol] } newtype StrRef problem = StrRef {unStrRef :: String} addRevref :: ref (Problem sol ref) -> Problem sol ref -> Problem sol ref addRevref ref (Problem f refs revrefs sol) = Problem f refs (ref:revrefs) sol modifyProblem :: Eq sol => (Problem sol (STRef s)) -> ST s (Bool,Problem sol (STRef s)) modifyProblem (Problem f refs revrefs oldsols) = ((oldsols /=) &&& Problem f refs revrefs) <$> f <$> mapM (liftM prsols.readSTRef) refs strRef2stRef :: [(String,Problem sol StrRef)] -> ST s (Maybe [(String,STRef s (Problem sol (STRef s)))]) strRef2stRef list = do list' <- mapM makeRef list solveRefR <- and <$> mapM (solveRef (map selsr list').selpr) list' return $ if solveRefR then Just $ map selsr list' else Nothing where makeRef :: (String,Problem sol StrRef) -> ST s (String,Problem sol StrRef,STRef s (Problem sol (STRef s))) makeRef (s,p@(Problem f _ _ _)) = liftM ((,,) s p) $ newSTRef $ Problem f [] [] [] solveRef :: [(String,STRef s (Problem sol (STRef s)))] -> (Problem sol StrRef,STRef s (Problem sol (STRef s))) -> ST s Bool solveRef list (Problem f strrefs _ _,stref) = case mapM (flip lookup list.unStrRef) strrefs of Just strefs -> writeSTRef stref (Problem f strefs [] []) >> return True Nothing -> return False selsr (s,p,r) = (s,r) selpr (s,p,r) = (p,r) makeRevref :: STRef s (Problem sol (STRef s)) -> ST s () makeRevref stref = prrefs <$> readSTRef stref >>= mapM_ (flip modifySTRef (addRevref stref)) stsolve :: Eq sol => [STRef s (Problem sol (STRef s))] -> ST s () stsolve strefs = fst <$> runStateT stsolve' strefs where stsolve' :: Eq sol => StateT [STRef s (Problem sol (STRef s))] (ST s) () stsolve' = do task <- getNewTask case task of Just task' -> do (c,p) <- lift $ readSTRef task' >>= modifyProblem lift $ writeSTRef task' p when c $ modify $ nub.(prrevrefs p++) stsolve' Nothing -> return () getNewTask :: MonadState [task] m => m (Maybe task) getNewTask = do state <- get case state of [] -> return Nothing t:ts -> put ts >> return (Just t) solve :: Eq sol => [(String,Problem sol StrRef)] -> Maybe [(String,[sol])] solve ps = runST $ do ps' <- strRef2stRef ps T.forM ps' $ \ps'' -> do mapM_ (makeRevref.snd) ps'' stsolve $ map snd ps'' mapM (\(s,r) -> (,) s <$> prsols <$> readSTRef r) ps'' constPr :: [sol] -> Problem sol ref constPr s = Problem (const s) [] [] [] orPr :: Eq sol => [ref (Problem sol ref)] -> Problem sol ref orPr refs = Problem (foldl1 union) refs [] [] andPr :: Eq sol => [ref (Problem sol ref)] -> Problem sol ref andPr refs = Problem (foldl1 intersect) refs [] [] test1 = solve [ ("a",constPr [1,2]), ("b",constPr [2,3]), ("c",orPr [StrRef "a",StrRef "b"]), ("d",andPr [StrRef "a",StrRef "b"])]
で、これの話をコミケ原稿のネタにでもしようかなぁと考えています。(という事を理由に面倒な説明は書かない)
実は今回は二箇所で本を出す予定で、無事原稿が上がったらちゃんと告知を書くつもりです。頑張ります。
一通りいじり終わったと思うので、とりあえず現状を書いてみようと思う。
普段使ってるキーボードは白 HHKB Pro2 で、基本は QWERTY 配列の英語キーボードです。で、KeyRemap4MacBook を使って色々いじったのですが、
という感じで、大量のいらないキーを殺して Control と何かで代用しようとしています。とりあえず便利だと思う。
ついさっき tmux のソースコードを読んでいて、causelist という型の定義を探していたんですが、
#define ARRAY_DECL(n, c) \ struct n { \ c *list; \ u_int num; \ size_t space; \ }
という感じの邪悪なマクロがありまして、
ARRAY_DECL(causelist, char *);
などと書いてあるわけです。そりゃ見付からん、しかも中身文字列ってバカにしてるのかー!
で、何が言いたいのかというとですね、tags 系のツールがプリプロセッサ通した物を読んでくれればいいんじゃないかなぁと思ったりするわけです。
多分フィルタとして cpp コマンドを通せばいいだけなんですが、うっかり GNU Global のソースコード落としてきてしまって、読んでも良く分からないし困ったなぁ……。
アイディアだけ思い浮かんだのでメモ。
まず、ここで言う依存関係というのは、非形式的な説明をすると、
a = ... b = f a
のようなプログラムに関して、b の型の推論には a の型を利用する。といった関係の事で、このような場合において b は a に依存していると言う事にする。
このような場合にどういった順序で推論を行えばいいかと言うと、a -> b の順番である事は自明である。
そこで、依存関係のグラフを作り、その依存関係を辿って推論を行うような推論器が書けないかと考えた。
結論としては、恐らくできるのではないかと考えている。ST Monad の文脈内で STRef を使って参照を持ち、書き換え、依存関係に従ってタスクを積む。といった操作で実現されると考えている。
蛇足だが、今調べた所 STRef による参照オブジェクトは Eq クラスのインスタンスであり、比較が可能である。重複タスクの発生はこれによって防げる。
また、これに近い話として FRP という物があるとか、まあ眠くて日本語が書けてないのでとりあえず寝ようと思う。
Prolog+Haskell な言語。関数っぽく見える物が述語的にも振る舞う。(++)とか
perm :: [a] -> [a] perm [] = [] perm (x:xs) | l++r =:= perm xs = l++[x]++r where l,r free
問題は処理系が腐っているという事です。
