Hatena::ブログ(Diary)

菊やんの雑記帳

2010-05-22 Haskell勉強中

[] IOモナドの実装 03:46  IOモナドの実装 - 菊やんの雑記帳 を含むブックマーク

昨日がんばってIOモナドの実装がどうなってるのか考察したので、答えを見た

http://itpro.nikkeibp.co.jp/article/COLUMN/20070206/260872/

から参考文献をたどって

http://homepages.inf.ed.ac.uk/wadler/topics/monads.html#imperative

を読んでみたところ、昨日実装したのは継続を使ったIOらしい。IOモナドはもっと効率的に実装できて、それはほとんどStateモナドと同じだけどStateを更新するところを評価したところで、副作用のあるCの関数を呼ぶという実装で正しく動作することをモナドが保障してくれてるようだ。継続のほうとモナドのほうは昨日実装したように相互にエミュレートできる。

NiseIOはIOモナドを継続を使って実装し、executeNiseIOは継続をIOモナドを使って実装したということになってそうだ。

次はHaskellProject Eulerの問題を一問解いてみるかな。291とか適当実装では終わらなかったからちょっと考察して実装してみよう。

2010-05-21 Haskell勉強中

[] IOモナドが倒せない 03:37  IOモナドが倒せない - 菊やんの雑記帳 を含むブックマーク

色々入門書を読んでみたのだが、IOモナドというものがどういうものなのか分からない。

使い方は分かるんだが、なんでこうなってるのとか、どういう風に実装されてるのかとかさっぱり理解の外である。

ということで、まず、NiseIOモナドを自分で作って見てある程度自分で考えてから実装を見ないと損した気分になるので、考えてみた。

よくある入門書いわくIOモナド副作用実行前の世界と副作用実行後の世界+副作用の結果を考えることで純粋になってるらしい。

だが、まあ普通に考えてそういうインターフェース

data Env = Env {input::String, output::String }
data NiseIOResult a = NiseIOResult a Env

getChar_1 :: Env -> NiseIOResult Char
getChar_1 (Env (x:xs) y) = NiseIOResult x (Env xs y)

putChar_1 :: Char -> Env -> NiseIOResult ()
putChar_1 c (Env x y) = NiseIOResult () (Env x (c:y))

example_echo env =
  let NiseIOResult c  env'  = getChar_1 env in
  let NiseIOResult () env'' = putChar_1 c env' in
  example_echo env''

のように、副作用が環境を受け取って、新しい環境を返すようになってるものだと思う。

というか、副作用のある言語の意味論はこういう形に変換してから考えるものだったと思う。

まあこんな風に環境を陽に記述するようなやり方だと、明らかに環境が正しくリンクしてることを保障できないので論外なわけで、

これを正しくリンクさせるように制限したインターフェースがIOモナドだと思ってしまっていた。

これを元にしてNiseIOモナドを作ってみると

type NiseIO a = Env -> NiseIOResult a

instance Monad NiseIO where
  x >>= f = \env ->
    let (NiseIOResult v env') = x env in
      f v env'
  return x = \env -> NiseIOResult env x

getChar_2 :: NiseIO Char
getChar_2 = getChar_1

putChar_2 :: Char -> NiseIO ()
putChar_2 c = putChar_1 c

execute :: Env -> NiseIO a -> IO (NiseIOResult a)
execute env f =
  return (f env)

ってなったんだけど、これはなんだかおかしい。execute側がgetCharとかを実行してエミュレートしないといけないのにいれる場所がない。

だいたいこれStateモナドの劣化版じゃん。なんか作りたいものと違う。

作りたいのは

niseGetChar :: NiseIO Char
nisePutChar :: Char -> NiseIO ()
niseMain :: NiseIO ()
niseMain =
  do c <- niseGetChar
     nisePutChar c
     niseMain

executeNiseIO :: NiseIO a -> IO a

main = executeNiseIO niseMain

インターフェースで、偽アクションは無限リストみたいになってて

executeNiseIO 偽アクション
executeNiseIO (最初の偽アクション:残りの偽アクション)

ここで最初の偽アクションを実行する

executeNiseIO (最初の偽アクション:二つ目の偽アクション:残りの偽アクション)

ここで二つ目の偽アクションを実行する

みたいになってないと、Haskell処理系は実装できないと思うのですよ。

そうやって考え抜いてできたのがこれ

data NiseIO a = NiseIOReturn a
  | NiseIOGetChar (Char -> NiseIO a)
  | NiseIOPutChar Char (() -> NiseIO a)

instance Monad NiseIO where
  return x = NiseIOReturn x

  NiseIOReturn x >>= f = f x
  NiseIOGetChar g >>= f = NiseIOGetChar (\x -> g x >>= f)
  NiseIOPutChar ch g >>= f = NiseIOPutChar ch (\x -> g x >>= f)

niseGetChar :: NiseIO Char
niseGetChar = NiseIOGetChar NiseIOReturn

nisePutChar :: Char -> NiseIO ()
nisePutChar ch = NiseIOPutChar ch NiseIOReturn

niseMain :: NiseIO ()
niseMain =
  do c <- niseGetChar
     nisePutChar c
     niseMain


executeNiseIO :: NiseIO a -> IO a
executeNiseIO (NiseIOReturn x) = return x
executeNiseIO (NiseIOGetChar f) =
  do c <- getChar
     executeNiseIO (f c)
executeNiseIO (NiseIOPutChar c f) =
  do putChar c
     executeNiseIO (f ())

main = executeNiseIO niseMain

これならIOモナドの実装に近づけてると思える。多分