Hatena::Diary

Hatena::Diary::pi8027

 

2010-07-27

hoogle を便利に使いたい

具体的に何が不満かっていうと、データファイルを自分で作る方法が分からない上に、元々入っているデータが少な過ぎる。.hoo ファイルがそれっぽいけど、当然作るツールはあるんだと思うし、これはどうすればいいのかなぁ。

cabal で入れるついでに hoogle にも登録される! くらいできたらとても嬉しいんですが、できないかなー。

2010-07-25

推論器っぽい物のお話続き

とりあえず簡単な物から書いてみよう! という事で 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"])]

で、これの話をコミケ原稿のネタにでもしようかなぁと考えています。(という事を理由に面倒な説明は書かない)

実は今回は二箇所で本を出す予定で、無事原稿が上がったらちゃんと告知を書くつもりです。頑張ります。

2010-07-24

現在のキーマッピング

一通りいじり終わったと思うので、とりあえず現状を書いてみようと思う。

普段使ってるキーボードは白 HHKB Pro2 で、基本は QWERTY 配列英語キーボードです。で、KeyRemap4MacBook を使って色々いじったのですが、

  • Space to Shift_L (SandS)
  • Drop Shift_L
  • Drop Tab
  • Drop Escape
  • Drop Return
  • Drop Delete
  • Swap Semicolon and Colon
  • Control-H to Delete
  • Control-I to Tab
  • Control-[ to Escape
  • Control-M to Return

という感じで、大量のいらないキーを殺して Control と何かで代用しようとしています。とりあえず便利だと思う。

tags 不便で困った

ついさっき 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 のソースコード落としてきてしまって、読んでも良く分からないし困ったなぁ……。

2010-07-22

依存関係に基く推論を行う型推論器の実装 in Haskell

アイディアだけ思い浮かんだのでメモ。

まず、ここで言う依存関係というのは、非形式的な説明をすると、

a = ...

b = f a

のようなプログラムに関して、b の型の推論には a の型を利用する。といった関係の事で、このような場合において b は a に依存していると言う事にする。

このような場合にどういった順序で推論を行えばいいかと言うと、a -> b の順番である事は自明である。

そこで、依存関係のグラフを作り、その依存関係を辿って推論を行うような推論器が書けないかと考えた。

結論としては、恐らくできるのではないかと考えている。ST Monad の文脈内で STRef を使って参照を持ち、書き換え、依存関係に従ってタスクを積む。といった操作で実現されると考えている。

蛇足だが、今調べた所 STRef による参照オブジェクトEq クラスのインスタンスであり、比較が可能である。重複タスクの発生はこれによって防げる。

また、これに近い話として FRP という物があるとか、まあ眠くて日本語が書けてないのでとりあえず寝ようと思う。

誕生日

が近いです。7/28 です。

というわけで乞食になります。なんかください。

2010-07-04

Curry すばらしい

Prolog+Haskell な言語。関数っぽく見える物が述語的にも振る舞う。(++)とか

perm :: [a] -> [a]
perm [] = []
perm (x:xs) | l++r =:= perm xs = l++[x]++r where l,r free

問題は処理系が腐っているという事です。