[Haskell] State Monad

1. 类型

类型用来区分内存中对程序员来说不同种类的数据块
而内存中存储的是表达式的值
所以，区分内存块的类型，就是区分表达式的类型

静态类型，指的是在编译时就能确定表达式的类型
动态类型，指的是在运行时才能确定表达式的类型

注：
静态类型，也可以说，通过代码文本就能确定表达式的类型

强类型和弱类型是相对而言的
类型系统的强度指的是，在多大程度上能把表达式看做是合法类型的
类型强度的表现形式是，是否允许隐式类型转换
弱类型，更允许隐式类型转换
强类型，更不允许隐式类型转换

2. 定义类型

Haskell中定义类型的方式有以下几种

（1）使用type定义类型别名

type MyTuple = (Int, String)

定义MyTuple为元组类型(Int, String)的别名

（2）使用data定义新类型

data BookType = BookValue Int String

其中，BookType是类型名，又称为类型构造器，BookValue称为值构造器

一个BookType类型值，可以这样定义

let bookValue = BookValue 12 "ab"

注：
因为类型构造器和值构造器会在不同上下文中使用，所以经常把它们写为同一个名字

data Book = Book Int String

遇到名字Book时要小心区分

（3）使用newtype为已有类型定义新的标识
newtype定义的类型，只能有一个值构造器，且值构造器只能有一个字段

例如：
一个值构造器，值构造器只有一个字段，可以

newtype Okay = ExactlyOne Int

类型构造器有多个参数，但是只有一个值构造器，值构造器只有一个字段，也可以

newtype Param a b = Param (Either a b)

字段访问器语法，可以

newtype Record = Record {
    getInt :: Int
}

注：
字段访问器语法，同时定义了字段的类型Int，以及字段的访问器函数getInt :: Record -> Int
例如：
通过值构造器Record构造该类型的值，Record 12
通过访问器提取字段的值，getInt (Record 12)

有一个值构造器，但是值构造器没有字段，不可以

newtype TooFew = TooFew

有一个值构造器，但是值构造器有两个字段，不可以

newtype TooManyFields = Fields Int Int

有多个值构造器，不可以

newtype TooManyCtors = Bad Int
    | Worse Int

3. 带参数的类型

类型构造器也可以带参数

data Maybe a = Nothing
   | Just a

data Either a b = Left a
    | Right b

其中，Maybe是类型构造器，Maybe Int才是一个具体的类型
Either是类型构造器，Either Int String才是一个具体的类型

注：
与函数的Currying相似，类型构造器也可以Currying
Either是一个类型构造器，提供两个类型Int和String，得到类型Either Int String
Either Int也是一个类型构造器，提供类型String，得到类型Either Int String

4. newtype

使用newtype为已有类型定义编译时的新标识，
这个标识在运行时会转换为原有的类型，可以称为去壳

例如：
定义新的类型

data DataInt = D Int
    deriving (Eq, Ord, Show)

定义编译时的类型外壳

newtype NewtypeInt = N Int
    deriving (Eq, Ord, Show)

运行时，求值undefined会发生错误

ghci> undefined
*** Exception: Prelude.undefined

运行时，_可以匹配所有，undefined不求值

ghci> case D undefined of D _ -> 1
1

运行时，N外壳会去掉，即case undefined of _ -> 1，_可以匹配所有，undefined不求值

ghci> case N undefined of N _ -> 1
1

运行时，D _来匹配undefined的求值结果，undefined要求值，发生错误

ghci> case undefined of D _ -> 1
*** Exception: Prelude.undefined

运行时，N外壳会去掉，即case undefined of _ -> 1，_可以匹配所有，undefined不求值

ghci> case undefined of N _ -> 1
1

5. typeclass

类型类提取了相似的运算
类型类的实例是一个类型构造器，这个类型构造器构造的类型具有类型类指定的运算

注：
类型类的实例，是一个类型构造器
类型构造器，可以是零元类型构造器（具体的类型），也可以带参数

例如：

class BasicEq a where
    isEqual :: a -> a -> Bool

其中，BasicEq类型类，定义了isEqual函数

指定类型构造器Bool（零元类型构造器，即具体的类型）是BasicEq类型类的实例
于是，isEqual就具体化为isEqual :: Bool -> Bool -> Bool

instance BasicEq Bool where
    isEqual True  True  = True
    isEqual False False = True
    isEqual _     _     = False

6. Monad

Monad是一个类型类
针对一般化的链式操作，它定义了>>=和return两种运算

class Monad m where
    -- chain
    (>>=)  :: m a -> (a -> m b) -> m b
    -- inject
    return :: a -> m a

其中，Monad类型类的实例，是一个单参类型构造器

注：
m a类型的值，通常称之为action
有时候，返回action的函数，也称之为action

instance Monad Maybe where
    Nothing >>= f = Nothing
    Just a >>= f = f a
    return = Just

其中，>>=具体化为了(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
return具体化为了return :: a -> Maybe a
f的类型是f :: a -> Maybe b
Nothing和Just是Maybe a类型的值构造器

data Maybe a = Nothing
    | Just a

注：
Monad还定义了两种操作>>和fail

(>>) :: m a -> m b -> m b
a >> f = a >>= \_ -> f

>>并不关心a的执行结果，只是进行顺序调用

fail :: String -> m a
fail = error

7. do语法块

do语法块会在编译时转换为>>=，>>和return形式

（1）单个action

doNotation1 =
    do act

translated1 =
    act

（2）多个action

doNotation2 =
    do act1
       act2
       {- ... etc. -}
       actN

translated2 =
    act1 >>
    do act2
       {- ... etc. -}
       actN

finalTranslation2 =
    act1 >>
    act2 >>
    {- ... etc. -}
    actN

（3）带有<-的action

doNotation3 =
    do pattern <- act1
       act2
       {- ... etc. -}
       actN

translated3 =
    let f pattern = do act2
                       {- ... etc. -}
                       actN
        f _ = fail "..."
    in act1 >>= f

（4）let

doNotation4 =
    do let val1 = expr1
           val2 = expr2
           {- ... etc. -}
           valN = exprN
       act1
       act2
       {- ... etc. -}
       actN

translated4 =
    let val1 = expr1
        val2 = expr2
        valN = exprN
    in do act1
          act2
          {- ... etc. -}
          actN

8. State Monad

为原有类型定义一个新的标识

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

其中，类型构造器是State
字段的类型是s->(a,s)是一个函数
字段访问器是runState

注：
因为State是一个双参类型构造器，
所以State s是一个单参类型构造器
runState的类型是runState :: State s a -> s -> (a, s)

指定State s是Monad类型类的实例

instance Monad (State s) where
...

注：
Monad类型类的实例，是一个单参类型构造器，
所以，State s是Monad类型类的实例，State不是

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 -> let (a, s') = runState m s
                                                    in runState (k a) s'

其中，m的类型是m :: State s a
k的类型是k :: a -> State s b
runState的类型是runState :: State s a -> s -> (a, s)