ST Monad

首先在这里请允许我斗胆说一说Monad,这个概念在函数式编程流行的今天，已经在编程的过程中出现的越来越多，不过老实说，接下来的和Monad可能没啥关系，但是ST Monad确实是很实用的东西。

问题背景

在函数式编程中有一个问题相信一直困扰着像我一样的初学者，那就是函数式要求函数是纯函数，甚至有些语言还需要函数是Total的，也就是说一个函数同样的输出，必须有一个确定的输入(deterministic)。这一点可以增加程序分析工具，形式化工具的可用性，能够更加好的保证代码正确。但是这和一个我们在编程中必须要遇到的东西: 变量矛盾了，为什么？

int a = 0;
int adda (int b) {
    // do something
    a = a + b;
    // do something
    return a；
}
print (adda(1));
print (adda(1));

这里adda的输出对于相同的输入根本没法保持一致。
当然这种情况我们完全是可以避免的，因为这里的问题本质在于，我们允许了全局变量。函数内更新了外面的东西。当然这不是说这样我们对整个程序就没有办法验证分析程序正确性了，如果我们引入霍尔逻辑，即给出前后条件的方式其实还是可以继续讨论的。
但是很多时候，全局变量是完全没有必要的，完全可以通过值传递等方式取完成，我们在命令式编程里的很多做法其实是在逻辑上浪费了，比如上面的程序，传a进函数就可以了。

int adda (int a, int b) {
    // do something
    int c = a + b;
    // do something
    return c；
}
print (adda(0, 1));

print (adda(adda(0, 1), 1));

In Haskell

在haskell中表达带有顺序结构的函数当然是完全没有问题的，do block就可以。

adda a b= do 
    -- something
    let c = a + b 
    -- something
    return c

main = do
    print (adda (adda 0 1) 1)

ok , so far so good.
但是如果adda这个函数更加复杂，在函数内部也要对c进行改变呢？比如我们在一个循环中会对c做操作。

int adda (int b) {
    // do something
    c = a + b;
    // do something
   for(int i=0; i < 10; i++) {
       // do something
       c++;
   } 
    return a；
}

这时候haskell还想完全不使用变量，但是又想用顺序结构去完成就非常麻烦了。。。。。即使使用了函数式的写法，你也会不得不使用各种嵌套的递归，更加糟糕的情况是因为使用递归，大量的中间变量c会产生，这会增加gc的负担。

但是我们如果仔细思考一下，增加内部变量c真的会影响我们函数式编程纯的影响吗？
似乎并不会，最外面的adda这个函数的输入输出依然是确定的，从外面看，我们依然是safe的。而haskell也确实提供了这样一种折衷的思路， ST Monad,看个简单求和的例子吧

import Control.Monad.ST
import Data.STRef
import Control.Monad


sumST :: Num a => [a] -> a
sumST xs = runST $ do           -- runST takes out stateful code and makes it pure again.

    n <- newSTRef 0             -- Create an STRef (place in memory to store values)

    forM_ xs $ \x -> do         -- For each element of xs ..
        modifySTRef n (+x)      -- add it to what we have in n.

    readSTRef n                 -- read the value of n, and return it.

例子来自haskell wiki.
在runST包裹的do block中使用newSTRef，我们就可以得到一个变量啦，起码看起来是个真正的变量。

ST Monad其实也没有很神秘，他和书上常见的那种状态的表示，偏射没什么区别，只是他读状态很像IO，众所周知，IO是带魔法的不纯状态包裹（~~doc里直接称为deeply magical~~），通过一个converter, ST 被映射到IO上了，所以这里的变量操作最终是使用类似IO的方式实现。

有了变量，很多原地算法就可以实现了～

最后编辑于：2019.08.07 10:58:08