Haskell 状态Monad (State Monad)的理解

1、State s a数据类型

State s a是一种用来封装状态处理函数（又叫：状态处理器）：\s -> (a,s’)的数据结构，因为State封装的是一个状态处理器(state processor)而不是状态s本身，所以称State为State类型(type)是不准确的。

newtype State s a = State { runState :: s -> (a,s) }
-- 即：newtype State s a = State (s -> (a,s))

• State 的数据类型是通过 newtype定义的，也就是对现有类型的封装。该类型有两个类型参数：表示状态的类型参数 s 以及表示结果的类型参数 a。

• 通过 runState 访问函数可以从 State 类型中取出这个封装在里面的转换函数：\s -> (a,s’)，该函数接收一个状态参数 s，经过计算（转换）之后返回一个二元组(a, s’)：状态s下对应的返回结果 a 以及新的状态 s‘

---

2、State s的Monad实例

instance Monad (State s) where
return :: x -> State s x 
return x = state (\x -> (x, s))
-- return x = State $ \s -> (x,s)

(>>=) :: State s a -> (a -> State s b) -> State s b
pr >>= k = state $ \ st ->
   let (x, st') = runState pr st   -- Running the first processor on st
   in runState (k x) st'           -- Running the second processor on st'

• state :: (s -> (a, s)) -> State s a 即：把一个状态处理器封装成State数据类型

• return函数把结果x封装成一个State s x即State (s -> (x, s))的状态构造器

• 而 bind 函数的类型签名为：(>>=) :: State s a -> (a -> State s b) -> State s b
  大致相当于 State (s -> (a, s)) -> (a -> State (s -> (b, s))) -> State (s -> (b, s))