一体何番煎じか分かったもんじゃないけどMonadでStack (1)
前回のスタートHaskell第5回に触発されたので色々とモナドをいじっていこうっと♪~(´ε` )
おっと、触発されただけで別にマスターしてないので悪しからず。
まだ全然Monad理解してないのでツッコミなどあったら是非是非お願いします。
さて、状態を扱えるControl.Monad.Stateを使って基本的なデータ構造であるStackを実装してみる。
ご存知のとおりHaskellには状態という概念がないので、Monadを使ってシミュレートするわけだ。
とりま、型だけ書いとけ
今回実装する関数は、C++のSTLにあるstackを参考にpush,pop,top,size,emptyの5種類
とりあえずまぁ、Stackを扱うState Monadの型をかいてみよう。
module Stack where import Control.Monad.State (State, get, put, runState) data Stack a = Stack a (Stack a) | Empty deriving (Show) type MonadStack a = State (Stack a) a push :: a -> MonadStack a push = undefined pop :: MonadStack a pop = undefined top :: MonadStack a top = undefined empty :: MonadStack Bool epmty = undefined size :: MonadStack Int size = undefined
うん、いいんじゃない?コンパイラに怒られないし。
個々の関数の実装
では、関数行ってみよう
ちなみにgetは今の状態を結果として返してくれる関数で、putは引数を状態に設定して何も返さない関数ですよ。
push
push :: a -> MonadStack a push x = do stack <- get put $ Stack x stack return x
今の状態をgetでstackに束縛し、putで新しくxを追加したStackを状態として設定し、何となく引数をそのまま返しています。
最後はreturn ()のほうがいいですかね。
pop
pop :: MonadStack a pop = do Stack x stack <- get put stack return x
getで返された値をStack x stackでパターンマッチしてstackをputし、xを返しています。
top
top :: MonadStack a top = do Stack x _ <- get return x
上のpopのstackをputしないバージョンです。
size
size :: MonadStack Int size = get >>= (\stack -> return (size' 0 stack)) where size' x Empty = x size' x (Stack _ stack) = size' (x+1) stack
do記法を使わずに書いてみました。sizeは毎回計算しています。
empty
empty :: MonadStack Bool empty = get >>= (\stack -> empty' stack) where empty' Empty = return True empty' (Stack _ _) = return False
この辺も見たまんまです。2行目は
empty = get >>= empty'
のほうが単純だけど、わかりやすさのために上のような感じで書いてみました。
試してみよう
> runState (push 1 >> push 2 >> push 3 >> pop) Empty (3,Stack 2 (Stack 1 Empty)) > runState (push 1 >> top) Empty (1,Stack 1 Empty) > runState (push 1 >> push 1 >> size) Empty (2,Stack 1 (Stack 1 Empty))
うん、いいかんじ。
しかし問題が発生
お気づきになっただろうか?( ゚д゚)気づいた人はもういいです。
今までのコード、別にGHCにもぐもぐさせてコンパイルエラーはでないんだけど、すでに重大な問題がある。
例えば次の例
> runState empty Empty (True,Empty)
はいいんだけど、これはダメ
> runState empty (Stack 1 Empty) <interactive>:1:23: No instance for (Num Bool) arising from the literal `1' Possible fix: add an instance declaration for (Num Bool) In the first argument of `Stack', namely `1' In the second argument of `runState', namely `(Stack 1 Empty)' In the expression: runState empty (Stack 1 Empty)
あぁん!?( ゚д゚)
これ実はMonadStackのデータ型に問題があった。
type MonadStack a = State (Stack a) a
よく見るとStackの型変数とStateの二つめの型変数が同じaを使ってるじゃん。
これじゃぁStackに押しこむ要素とStackの操作関数の返り値が同じ型じゃないとダメということになる。
popやtopなんかはStackの要素と返り値が同じ型だから問題ないけど、emptyは返り値がBoolだからStack BoolのStackにしか使えない。
だからこれはOKだけど上のはダメと。
> runState (push True >> push False) Empty (False,Stack False (Stack True Empty))
なるほどなるほど。さっきsize関数がOKだったのもStackの要素と返り値が偶然Intで一致したからなんだね。
だからこれはダメ。
> runState (push True >> push False >> size) Empty <interactive>:1:38: Couldn't match expected type `Bool' with actual type `Int' Expected type: Control.Monad.Trans.State.Lazy.StateT (Stack Bool) Data.Functor.Identity.Identity a0 Actual type: MonadStack Int In the second argument of `(>>)', namely `size' In the first argument of `runState', namely `(push True >> push False >> size)'
ちょっと分かってきたところで修正したモノはまた次回でヽ(´ー`)ノ