ST Monad

作者: 卷毛宿敌大小姐 | 来源:发表于2019-08-07 10:53 被阅读0次

首先在这里请允许我斗胆说一说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的方式实现。

有了变量,很多原地算法就可以实现了~

相关文章

  • ST Monad

    首先在这里请允许我斗胆说一说Monad,这个概念在函数式编程流行的今天,已经在编程的过程中出现的越来越多,不过老实...

  • 函数式编程下的visitor模式

    在深入理解函数式编程之monad中,我们详细讲述了monad模式,以及monad模式和functor模式之间的区别...

  • 函数式内功心法-00: 万物互连之monad创世纪

    很多人学习haskell,都会在monad这个概念上迷失。真是天下苦monad久矣! 人们常常说 Monad不就是...

  • Monad 定律

    monad 是支持>>=操作的 applicative 函子,>>=读作绑定,它的类型是: 即取一个 monad ...

  • Reader Monad

    本文使用Haskell语言,并需要读者有Monad的基本概念 什么是Reader Monad 在介绍Reader之...

  • 【函数式】Monads模式初探——Option Monad

    Option Monad Scala中的Option是一个Monad实现。Option的简化版定义如下: 代码中,...

  • 理解范畴论中单子需要的最小知识集

    A monad is just a monoid in the category of endofunctors,...

  • monad

    函子:对map函数的泛化在第一部分和第二部分实现了一些不同组合子库。这些组合子的相似性是值得注意的,比如为每个数据...

  • Monad

    Monad不就是个自函子范畴上的幺半群,这有什么难理解的(A monad is just a monoid in ...

  • 阅读源码之: ReactiveObjC第三篇RACSignal

    RACStream 是抽象类,基类,代表任意流,代表monad, 在其上构建基于流的操作 monad/ 单子 基于...

网友评论

      本文标题:ST Monad

      本文链接:https://www.haomeiwen.com/subject/abkgdctx.html