読者です 読者をやめる 読者になる 読者になる

りんごがでている

何か役に立つことを書きます

一体何番煎じか分かったもんじゃないけど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)'

ちょっと分かってきたところで修正したモノはまた次回でヽ(´ー`)ノ