STはState Transformerとは言うけれど

少し前に巷ではやったSTのことを勉強してみました。原典のLazy Functional State Threadsをかじってみました。

僕はStateモナドはなんとなく自分でかけるくらいまで理解していたのですが、STは使ったこともないし、いったい何物なんだかぜんぜん知りませんでした。

Stateモナドは要するに関数なわけで
State s a = State \s -> (a, s)

ということはStateモナド系のKleisli関数がバインドされる図は乱暴な見方をすればこうゆう絵柄になるわけです。

runState (\s -> (a, s') >>= \a s -> (b, s') >>= \b s -> (c, s'))

何をスケッチしてるんだかよくわからなくなっちゃうんですがここではそれぞれのKleisli関数をそのシグネチャだけで書いています。それぞれのKleisli関数は（Kleisli関数なので）パラメタ１つとステートをもらってステートと何かほかの値のTupleを返すようになっているので、基本的には違うステートや何か値を下流のKleisli関数に流すことができますね。でもやっていることは単に関数をつなげているだけなので、まるっきり純粋関数型です。でも、見方によったら変数の値が変わっているような気もしなくもない…

モナドでTransformerというとMaybeTとかListTみたいなモナド同士を合成するタイプクラスを思いつきますよね…だから僕も最初はSTは単純にStateのTransformerなのかと思ってたんですが、これが違うことはちゃんとSTのシグネチャをほかのMonadTransformerと比較するとはっきりしてきます。おまけにStateTもControl.Monad.Stateモジュール内に定義されています…

newtype MaybeT m a
newtype StateT s m a
newtype State s a
data ST s a

こうやって見るとMonadTransformerであるStateTはSTよりも型パラメタが一個多いですよね。そして、STとStateはシグネチャ的には同じです。このことから、STがMonadTransformerではないことがはっきりしますね。
しかしながら混乱するのは原典のほうを当たってみるとSTをたびたびState Transformerという呼び方をしているわけです。これだと「あー、これはきっとState Monad Transformerのことを言ってるに違いない」と思っちゃう人がいてもおかしくないですよね…しかしながらこの論文の日付は１９９３年、論文の中でもモナドのバインドすら出てきません。そんなことから推察するに、この論文が書かれたころにはまだMonad Transformerのほうが生まれてすらいなかったんじゃないかと…

前説が長くなっちゃったんですが、論文で説明されているSTの考え方は大体こんな感じです…

あるステートを孤立した「スレッド」の中に閉じ込めてしまうと、そのスレッド内でどんなことがおきていてもスレッドの外側からは何も変化しているようには見えない。僕たちが知っているStateモナドの保有している状態をこういったスレッドの中に閉じ込めてしまうと安全に刻々と変化する状態をうまく表現できる。

見たいな事が書いてあって、さらに理論的な安全性の検証みたいなことが書いてあります。

そして何より何も知らなかった僕にとって衝撃的だったのは

newtype IO a = ST RealWorld a

と言うことです。つまり、IOはSTで実装されている。といっても、今のGHCの中身が実際どうなってるのかは知らないですが…

以前からIOについて漠然と思っていたことのひとつに、副作用のあるものはみんなIOといっても、アドレス0x10000000にある１バイトの値はアドレス0x20000000にある１バイトの値とは独立に変化すると考えるのが自然なはずなのに、メモリを書き換える操作がIOモナドであるためにこの２つの操作の実行順序がdeterministicに決定されているようにしかコードがかけないのはなんだかおかしいんじゃないか…（ちょっと突っ込みどころ満載かもしれませんが、まぁ、漠然と思っていることということで…）なんて思っていたんですが、こういったモデルをSTモナドは割りと正確に表現しているような気がしますね…

論文を読むとrunSTの定義：
runST :: (forall s. ST s a) -> a
に出てくる forallがそのSTモナドが保持している状態がほかから見えないことを証明することに役立っているようなことが書いてありましたが、そこのところは、まだちょっとわかんない感じです…

きょうはこのへんで。
ではでは。

Data.Treeを初期化する方法を工夫してみた

詳しいことはそのうち書くとして、ReaderモナドとStateモナドの違いなんかを考えているうちにXMLやHTMLの記述を簡略化するDSLみたいなものがあったらいいなと思ったりしていたら、どちらのブログかは失念してしまったのですが、たしかmoeというライブラリがまさしくそれをやってるということがわかってしまって、ここに書いてあることはまったくの焼き直しになってしまうのですが、まぁなんとか自力でここまでやってきたので、一応かいときます。

スタンダードライブラリの一部に、Data.Treeというのがあって、

Data Tree a = Node { 
	rootLabel :: a
	subForest :: [Node a] }

といった型になっているわけです。

このTree型のデータを初期化したいと思ったら、一番単純な方法はこんなことをやるわけですね:

tree = Node "n1" [
	Node "n2-1" [
		Node "n3-1" [ ], 
		Node "n3-2" [ ] ] ],
	Node "n2-2" [ ] ]

ほかにもData.Treeにはunfold系の関数でTree型のデータを構築できるようになっていたり、TreeはReadのインスタンスだったりするわけですが、コードに直接データを書き込まなきゃいけないときにもうちょっと便利になったらいいなと思って、こんなことができるようにしてみました。

tree = node "n1" $ do
	node "n2-1" $ do
		node_ "n3 -1"
		node_ "n3-2"
	node "n2-2"

main = putStrLn $ drawTree $ buildtree tree

括弧がなくなる分すっきりするのがまぁ、良い所といった感じでしょうか…ほんとはdoだけでやりたかったのですが、$をつけないとコンパイルしてくれません。かといって、ndo = $ do などということは受け付けてくれないだろうし…(って、試したわけではないんですが…)

中身はこんな感じになってます:

import Data.Tree
import Control.Monad.State.Lazy

el :: a -> State ([a] -> [a]) ()
el a = modify (\f -> f . (\as -> a : as))

nul = return ()

node :: a -> State (Forest a -> Forest a) () ->
　　　 State (Forest a -> Forest a) ( )
node a f = el $ Node a (buildForest f)
node_ a = node a nul

buildForest :: State ( [a] -> [a] ) () -> [a]
buildForest f = (snd $ runState (f) id) [ ]

buildTree = head . buildForest

Node型の中身の子Nodeのリストを生成する部分をモナド化しています。

中身としてはStateモナドを使って、ステート値の中にリストを作りこむ関数を構築しています。単純にステート値をForest aにしてしまうという方法を最初はとっていたのですが、難点はできあがったForestの中身の順序が記述と逆に出来上がってしまうので、reverseを呼ぶ羽目になるところです。reverseがいやだなーと思って、いろいろ試しているうちにたどり着いたのが、今回のやつなんですが、上記の方法でも、関数のビルドアップはelの中で逆順につながっているので、コスト的には変わらないように思います。ほんとにコストが気になったらData.Sequenceを使うといいんでしょうか、でも結局リスト方に戻す時点でコストがかかっちゃいますね…さらに、Stateモナドとかいろんなもので元データをくるんでいるので、生のNode型でデータを指定するよりはだいぶコストがかさんでるのかもしれません。簡潔性を追及したかったということで…

モナド型なのでreplicateM_なんかを使って繰り返してみたりとか、guard, when, unlessなんかを使って条件分岐なんかもできますね…

ではでは。

関数じゃなくてもモナドになれる

また、間が開いちゃったんですが、少し前にどんな関数でもモナドになれる件をかいたのですが、今回、さらに一歩進めて、ただの値でもモナドになることを書きたいと思います。

ということでこちら：

newtype V a = V {unv :: a}

instance Monad (V) where
	return a = V a
	(V v) >>= f = f v

モナド則のほうもちゃんと満足してくれそうですね。

#1 return a >>= k == k a
return a >>= k 
=> V a >> k = k a

#2 m >>= return == m
m >>= return 
=> V a >>= return = V a = m

#3 m >>= (\x -> k x >>= h) == (m >>= k) >>= h
m >>= (\x -> k x >>= h)
=> V a >>= (\x -> k x >>= h)
=> k a >>= h
(m >>= k) >>= h
=> (V a >>= k) >>= h
=> k a >>= h

といった感じなのですが、なにぶんIntなどの値のモナドなのでKleisli関数(:: a -> m b)はa -> V bといった感じで普通の関数になりますね。

ちなみにこのモナドではdo文では常に最後の計算結果が返り値になります。>>=を使う以外にあんまり使い道はなさそうですね…それですら(.)がすでにありますが…

ではでは。

モナドの分類

モナド型クラスに属する型はいろいろとあって、その中にはさらにMonadPlusをサポートするモナド型があったり、そうでないものがあったりするわけで、これはつまりいろいろなモナド型を２種類に分類しているわけですよね…

IO (Maybe a)という型のモナドのコードを書いていて、どうやらモナドのもうひとつの分類法があることに気がつきました(というほどすごいことではないんですが)。
その分類方法というのはつまり、そのモナド型が関数を内包しているかしていないかというものです。分類してみるとState、IO、Reader、Writer（たぶん）なんかは関数を内包しているモナド型で、リストやMaybeなんかはそうではないタイプのモナド型といった感じになります。でも、これはMonadPlusのように別の型クラスに表現できるようではなさそげです。

それで、いったいこれがどうゆう影響を及ぼすかというと、関数内包型のモナドは重ね合わせるのが結構めんどくさいということです。[Maybe a]とかMaybe [a]なんかは結構単純にできちゃうと思うんですが、IO (Maybe a)とか、IO（State a)とかは結構ややこしいことになってきます。逆にMaybe(IO a)なんかはそんなに酷いことにはなりませんな…でもState (IO a)はやっぱり大変かも…

それじゃあIO (Maybe a)は大変だからMaybe (IO a)にしようとか言ってみると、意味的には微妙な違いがありそうですね…僕がやろうとしていたことにはどっちでも使えそうなんですが、まだ試してません。

今日はつぶやき系でした…
ではでは。

実は関数もモナドとして捉えることができる

関数(a->b)はそのままArrowのインスタンスになっているわけなんですが、実はモナドのインスタンスとしても機能できることに気づきました…

ステートモナドとかを見れば何の秘密にもなっていないことなんですが…「関数もモナドのインスタンスとして扱える」という認識が今まではっきりとはなかったのでちょっとインパクトがありました…

ということでやってみました：

newtype MonadF i o = MonadF {runMF :: i -> o}

instance Monad (MonadF i) where
	return a = MonadF $ const a
	(MonadF af) >>= b = MonadF $ \i -> (runMF $ b $ af i) i
 
instance Functor (MonadF i) where
	fmap f (MonadF mf) = MonadF $ \i -> (f . mf) i

instance Applicative (MonadF i) where
	pure = return
	f <*> b = f >>= \f' -> b >>= \b' -> return $ f' b'

ついでにFunctorとApplicativeのインスタンスにもしちゃいました。ステートモナドの例に倣って関数のパラメタを隠蔽しちゃうことができるんですね…

ちなみにMonadF自身は(a->b)な関数をモナド化します。面白いのはバインド(>>=)の右辺にくるやつ（Kleisli関数？）のタイプが(a -> MonadF b c)つまり(b -> a -> c)という型の関数になるわけですね…

ちなみに使ってみるとこんな感じ：

testMF = (MonadF (+1)) >>= \j -> (MonadF (* j))

main = do
	print $ (runMF testMF) 2
	print "is equivalent of"
	print $ (\i -> (i + 1) * i) 2

ちゃんとバインドを使ってMonadF同士を結合できてますね。testMFのなかではパラメタが隠蔽されてますね…

いやー、いったい何がうれしいんでしょうか？教えてください。
ではでは。

と、ここまで書いてわかったのですが、実はこれ、Readerモナドというものとそっくりですね…Readerのほうは((->) r)という形で関数がインスタンスに取り込まれています。ちなみにReaderはMonadReaderのインスタンスで、MonadReader経由でlocalというメソッドが提供されています。これは暗黙変数に関数を適用した結果のをつかってモナドを実行することができるらしいです…ライブラリにも定義されているので便利なときもあるんでしょうね…

unwordsのコスト

Haskellで遊ぶよ さんのunwordsはO(n^2)?を読んで、unwordsのコスト、僕も考えてみました。コストはひょっとしたらO(n)なような気がしています。なぜかというと、unwordsがfoldrを使っているからかもと…間違ってるかもしれませんが…

foldrはright associativeなので、

foldr1 (++) ["a", "b", "c", "d"] = "a" ++ ("b" ++ ("c" ++ "d"))

ということになって、さらに++もright associativeで

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

なので、それぞれの文字列は１回ずつしかスキャンされていないような気がします…さらに遅延評価なのでリストの結合も使われる部分だけしか行われないですね…

これがfoldl1なんて使っていたら確かにO(n^2)になりそうですね…Associativityが右か左かでコストが変わってしまうのが面白いですね。今まであんまり理解しようとしていなかったのでよい勉強になりました。

時間を見つけて実際に実行時間を計測してみたらもっとはっきりしますね…

ずらしてみよう

ずいぶんとご無沙汰様になってしまいましたが、まだまだ遊んでますよー。Haskellで…

Haskellで遊ぶよさんの　takeWhile2とdropWhile2 を読んでいてちょっと前にどこかのプレゼン資料で見たちょっと感心したテクニックを思い出しました…

takeWhile　のシグネチャは
takeWhile :: (a -> Bool) -> [a] -> [a]

で、takeWhile2はしたがって
takeWhile2 :: (a -> a -> Bool) -> [a] -> [a]
というようにパラメタを二つとるtakeWhileというわけなんですが、この「テクニック」を使うとtakeWhileを使ってtakeWhile2のようなことをできるようになります。

種明かしをしてしまうとそんなに威張ることじゃないんですが、（おまけに自分の思いつきでもないし…）、入力のリストを「ずらす」んですね…

たとえば:
(\a -> zip a a) [1..]
とやると、当然のごとく:
[(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9),(10,10), ..]
となりますね…

これをちょっとひねって、

(\x -> zip x (tail x)) [1..]

とやると何が起きるでしょう？zipにわたる２つ目のリストは先頭要素が取り除かれているので、ひとつ「ずれて」いますね…ということで
[(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10),(10,11), ..]
となります。

とすれば、takeWhile2 は次のようにも書けることになりますね…

takeWhile2 :: (a -> a -> bool) -> [a] -> [a]
takeWhile2 f a = map snd $ takeWhile (uncurry . f) $ (\x -> zip x (tail x)) a

ただ、takeWhile2でちょっと悩ましいのはtakeされるのが 評価関数の第一パラメタにわたる値なのか第二パラメタにわたる値なのか、どっちがいいのかは結構その場その場で変わってきそうなところのような気もしますね…

この、「ずらす」トリックは面白いんですが、タプルを使う分効率が悪くなるようにも思われます…

今日はこの辺で。
ではでは。