Fleurer.Lee

老师：Monad想到什么呢？
同学：毛茸茸的猫猫!

好同学们，请默念“Warm and Fuzzy”100遍~

。。
。。
。。
。
。
。
。
。
。

。
。
。
。。
。。

100遍了没。。。好，我们先看看State猫猫的类型吧 ^_^

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

里面有个难看的record syntax，咱们无视之，改成：

data State g v = State (g -> (v, g))

就是一个lambda，外加一二元组：v表示猫猫正经计算中的值，g就表示猫猫的状态啦(就一个全局变量嘛)~那个lambda的参数g也一样。相应的猫猫Instance也就是如下：

instance Monad (State g) where
    return v = 
        State $ \g -> (v, g)
 
    (>>=) (State m) f = 
        State $ \g -> 
                let (v, g') = m g
                    (State m') = f v
                in  m' g'

还是一环套一环，函数编程没有变量，那就向下传递的时候改变它的值就行了。再加两个小喽骡：

get_g = State $ \g -> (g, g)
set_g v = State $ \_ -> (v, v)

全局变量的值不也在那个lambda的参数里么，get_g它设成计算中的值，这样在do-notation中就可以g <- get_g了。set_g则是把它的参数设到g里，而原先的g无视扔掉即可。

加个函数试验下：

run (State m) i = m i 
 
add1 :: State Int Int
add1 = do {
    g <- get_g;
    set_g $ g + 1;
}
 
add3 = do {
    add1;
    add1;
    add1;
}

进ghci输入run add3 1可得(4,4)，可见那个“全局变量”就这么变化了。

回头再想想它的类型，一个二元组不就够了嘛，为什么要套那层lambda呢？试下就知道

data State g v = State (g, v) 
 
instance Monad (State g) where
    (>>=) (State (g, v)) f = (g, f v)

看着不错，接着来：

    return v = ...

发现问题了没，return我们实现不了…搞不到原先g的值，链子就断在了这一环。解决方法就是把它推后，不是没有g么，于是放到参数里等着别人(>>=)给，这算不算惰性呢？ :)

ps:明白了State是怎么回事，附一山寨parsec ^_^ http://github.com/Fleurer/FParser

去年听王猫猫讲过之后就一直心安理得再也没看过Monad，以至于到昨天还不知State Monad为何物…囧

关于State Monad，似乎见过的教材都是拿随机数作例子，拿Monad跟一堆let对比，满眼的二元组绕啊绕啊，我给你个Monad让它不那么绕（存疑）～其实什么东西理解不了，往往就是因为不知道它怎么用（比如复变函数 =”=）

换个例子，像那个筛掉一个List中重复元素的nub函数多好….在命令式语言下边大约是这样：

def nub(xs)
    result=[]
    for x in xs
        if not result.include? x
	     result << x
    return result

若在函数式语言下边，用迭代大约是这样：

inub :: (Eq a) => [a] -> [a]
inub = inub' [] 
inub' rs [] = rs
inub' rs (x:xs) 
    | x `elem` rs    = inub' rs xs
    | otherwise     = inub' (rs++[x]) xs

inub’这个函数中有个rs参数，就相当于前面那个result变量。它的值会随着迭代发生改变，不同之处就是ts是引用透明的没有副作用。每次函数调用就是一个状态，状态就是一个值。

不喜欢给函数多加个参数怎么办？State Monad可以做到。在State Monad里面有两个函数可以使用：put，设置当前状态的值；get，获得当前状态的值。就相当于给函数加了一个（只有一个）可变的全局变量，在调用别的函数或者递归时这个值可以保留。

State Monad版本（我没觉得好看 =”=）：

mnub :: (Eq a) => [a] -> [a]
mnub xs = evalState (mnub' xs) []
mnub' [] = get
mnub' (x:xs) = do {
    rs <- get;
    if x `elem` rs then (do {
        mnub' xs;
    })
    else (do {
        put $ (rs++[x]);
        mnub' xs;
    });
}

原理大约就是do-notation中的每个语句都是用一个wrapper的类型包起来再不断往下传递么，而State的wrapper就是个类型为(a,s)的二元组（外加一层lambda？），每个语句的返回值放到s里，那个全局的值则放在a里…具体还有点迷糊，哪天推导下再说好了 >_<

Feather 2009-07-19 21:46:08

世事恰如迷局, 寻人, 失散, 流落, 皈依, 纷乱无绪, 及至谜底解开, 那人却已站立在你面前.

Read the rest of this entry »

作者：Neil
翻译：ssword
原文：http://neilbartlett.name/blog/2007/04/11/haskell-an-imperative-language-with-mutable-state/

Haskell是一门惰性的纯函数式语言，也就意味着其中没有可变的变量。呃，有，没有？看下这个Factorial的haskell实现吧：

fact n = runST (do
    r < - newSTRef 1
    for (1,n) (\x -> do
       val < - readSTRef r
       writeSTRef r (val * x))
    readSTRef r)

嗯，我可没说这样写好。实际上，这样写很糟糕，一行纯函数式代码就可以漂亮的搞定同样的工作。不过请注意下这代码与命令式语言是如何的相像，如对“可变变量”r的破坏性更新。再贴一下，与同等的C代码做个对比：

 
fact n = runST (do               | int fact(int n) {
     r < - newSTRef 1             |    int r = 1;
                                 |    int i;
     for (1,n) (\x -> do         |    for(i=1;i< =n;i++) {
         val <- readSTRef r      |
         writeSTRef r (val * x)) |       r = r * i;
                                 |    }
     readSTRef r)                |    return r;
                                 | }

瞧，你几乎可以把C的代码一对一地翻译成haskell。不过得承认，haskell的语法要猥琐些。

这一切是如何做到的呢？答案就是ST monad，有了它就可以写出有内部状态更新而对外仍保持纯粹的算法。runST函数是亮点，它创建了个初始的空状态，然后执行一系列的状态转换，到最后再销毁它。fact依然是Int->Int的纯函数，依然保留了引用透明。

另一个亮点是那个“for”，看起来跟个关键字一般，不过它本质就是一普通函数，定义如下：

for :: (Int,Int) -> (Int -> ST s ()) -> ST s ()
for (i,j) k = sequence_ (map k [i..j])

同理，我们也可以定义出foreach，if，while等等。有haskell这般强大的表达力，没必要再将控制流的操作定义为语言的关键字；我们甚至可以根据自己的需求来发明新的控制流程。

不过你看出来了没？没人会正二八经地像上面那样实现factorial。而且，我们真的希望如这般曲解haskell，以取悦从C过来的老程序员么？

是的，问题就在这里。有这项技巧，是为那些已知难以使用函数式风格或递归搞定的算法提供的折衷。同样，很多算法需要用到数组—–有限的内存和固定的访问时间—–使其更易于处理。在ST monad中实现数组很容易，但在传统的纯函数式代码中就要困难多了。（UPDATE：Cale说，纯代码中实现不可变的数组还是很容易的，只有可变的数组实现其来才困难）。

恩，ST monad和STRef表示了外部不可见的局部状态，那么全局的可变状态呢？我们可以用IO monad和IORef做到。当然，在用IO的时候就没有像runST那样回到纯代码的函数了[1]。

对我，这引发的思考就是：haskell是真正的纯函数式语言吗？我觉得不是—–它超越了纯函数式。它是既允许命令式编程，又使用强大类型系统来把有副作用的代码与纯代码分离。这一点，令它强大无比。

[1] 这不是绝对…其实有个方法：unsafePerformIO。不过我觉得应该辩证地讨论它。

所谓三人成虎，monad就是了。

先烈告诉我们，玩haskell，不用学monad；玩monad，不用学范畴论。当年不懂事啊，正被functor态射范畴这堆鬼东西折磨的半死的时候，突然就骂了出来：“妈的，这还是编程么？数学的拉去见学院派大胡子去！”

嗯，咱是程序员。学院派大胡子去死。嗯。

12Dec06
16:20:11 [Botje] monads have to be the singly most tutorialized feature _EVER_

好吧，这里只谈副作用（不过貌似monad还真避不开）。只是我自己的理解，不保证正确。大牛和小白请直接略过。

纵然大牛们反复重申monad不是为副作用而生，但相信大部分人一定是从IO那里才认识的monad。那么什么才是副作用呢？有个装逼（装纯？）的概念，那就是“引用透明”(reference transparency)。如果拿固定的参数调用一个函数，得到的结果一定是相同的。如果拿相同的参数调用同一个函数两次而得到的结果不一样，那么这个函数就是有副作用的。

如ruby的gets函数，它没有参数，返回一个string。每次执行（参数都是为空）返回的结果不一定一样（决定权在你的输入了），所以说它就没有引用透明。

看下Haskell中getLine函数的类型：

getLine :: IO String

和gets不一样，它返回的类型是IO String而非直接的String。先想一下，如果它的返回类型是String会怎样？你就可以把getLine函数塞到四处都是，可以让每个函数的结果都与输入有关。好吧，引用透明呢？见大胡子去了。

IO是个类型构造子，仅仅是把后面的String包起来。如果你输入“Alpaca”，它就返回IO “Alpaca”。怎样从中取出”Alpaca”来呢？像List，Maybe之类就直接上模式匹配就可以了，而所谓模式匹配就是匹配类型构造子。你可以let (x:xs)=alist\，但不可以let (IO str)=getLine。因为IO类型构造子在模块中没有被导出，换句话说，它是“私有”的，就像OO中把构造函数私有一样，只有那个模块里面的函数才可以访问它。这样一来在外面的你就不能从getLine中取值了。那该怎么办？里面有>>=。它可以把你的操作塞到里面去，可就是不让你从把里面的值带到别处。

getLine >>= (\str -> {-- your operation here--})

在这里>>=的实现大致就是这样（假设>>=只为IO存在）：

>>= :: IO a -> (a -> IO b) -> IO b
IO a >>= f = f a

它可以把函数串成一条链，并限制函数f的返回类型必须还得是IO。这样，与外界交互的一切代码就都被迫标上了个IO的标记。不是从外面取值，而是往外面传操作，操作完了再把它包好原样扔回去。而在haskell的纯洁世界中，外面的值是完全无法访问的。