[Haskell] State Monad和状态转移过程

初识状态

先看一个小游戏，这个小游戏用字符串来控制，最后得到总分。
c用来启动和停止计分，在启动计分状态下a加一分，在停止计分状态下b减一分。
本例中用abcaaacbbcabbab控制，最终得分为2。

module Main where
import Control.Monad.State

-- Example use of State monad
-- Passes a string of dictionary {a,b,c}
-- Game is to produce a number from the string.
-- By default the game is off, a C toggles the
-- game on and off. A 'a' gives +1 and a b gives -1.
-- E.g 
-- 'ab'    = 0
-- 'ca'    = 1
-- 'cabca' = 0
-- State = game is on or off & current score
--       = (Bool, Int)

type GameValue = Int
type GameState = (Bool, Int)
 
playGame :: String -> State GameState GameValue
playGame []     = do
    (_, score) <- get
    return score
 
playGame (x:xs) = do
    (on, score) <- get
    case x of
         'a' | on -> put (on, score + 1)
         'b' | on -> put (on, score - 1)
         'c'      -> put (not on, score)
         _        -> put (on, score)
    playGame xs
 
startState = (False, 0)
 
main = print $ evalState (playGame "abcaaacbbcabbab") startState

定义State Monad

-- 's' is the state, 'a' is the value
newtype State s a = State {
    runState :: s -> (a, s)
}

returnState :: a -> State s a
returnState a = State $ \s -> (a, s)

bindState :: State s a -> (a -> State s b) -> State s b
bindState m k = State $ \s -> runState (k a) s'
    where (a, s') = runState m s

instance Monad (State s) where
    m >>= k = bindState m k
    return a = returnState a

注意其中某些值的类型：

runState :: State s a -> s -> (a, s)
m :: State s a
k :: a -> State s b

还需注意，State s a中的s是类型，而\s -> ...中的s是值。

单步状态转移

-- runState (return 'a') 1 = ('a', 1)
return :: a -> State s a
return x = State $ \s -> (x, s)

-- runState get 1 = (1, 1)
get :: State s a
get = State $ \s -> (s, s)

-- runState (put 5) 1 = ((), 5)
put :: a -> State s ()
put x = State $ \s -> ((), x)

-- evalState (return 'a') 1 = 'a'
evalState :: State s a -> s -> a
evalState s = fst . runState s

-- execState (return 'a') 1 = 1
execState :: State s a -> s -> s
execState s = snd . runState s

用do-notation组合多步转移

因为(State s)是Monad的实例，
所以，类型State s a的值是一个monad value（也称为action
action中包装了类型为a的值。

do-notation可以把各个action串联起来。
还可以提取各action中包装的值，进行传递。

-- runState (do {put 5; return 'a'}) 1 = ('a', 5)
-- runState (do {x <- get; put (x+1); return x) 1 = (1, 2)
-- runState (do {x <- get; put (x-1); get) 1 = (0, 0)

这里详细解释一下runState (do {put 5; return 'a'}) 1的执行过程，

-- put 5 = State $ \s -> ((), 5)
-- return 'a' = State $ \s -> ('a', s)

-- do {put 5; return 'a'} 
-- = (put 5) >>= (\_ -> (return 'a'))
-- = (State $ \s -> ((), 5)) >>= (\_ -> (State $ \s -> ('a', s)))
-- = bindState (State $ \s -> ((), 5)) (\_ -> (State $ \s -> ('a', s)))
-- = State $ \s -> runState ((\_ -> (State $ \s -> ('a', s))) a) s' where (a, s') = runState (State $ \s -> ((), 5)) s
-- = State $ \s -> ('a', 5)

-- runState (do {put 5; return 'a'}) 1
-- = runState (State $ \s -> ('a', 5)) 1
-- = ('a', 5)

总结

evalState 状态转移过程 初始状态，从初始状态出发，最终得到一个结果值，
execState 状态转移过程 初始状态，从初始状态出发，最终得到一个结果状态，
runState 状态转移过程 初始状态，从初始状态出发，最终得到一个元组(结果值, 结果状态)。

而状态转移过程可以是状态的单步转移，也可以是用do-notation串联起来的多步转移。
因此，State Monad的做法，可以看做将状态转移过程固化下来，最后再一次性从初始状态转移到最终状态。

参考：

State Monad - HaskellWiki