ST Monad ==代码味道？

 

我正在Haskell中实现UCT算法，这需要相当数量的数据杂耍。 在没有深入细节的情况下，这是一个模拟算法，在每个“步骤”中，根据某些统计属性选择搜索树中的叶节点，在该叶中构建新的子节点，并根据新叶子及其所有祖先都会更新。

考虑到所有这些杂耍，我并不十分清楚如何让整个搜索树成为一个不错的数据结构。 相反，我一直在玩ST monad，创建由可变STRef组成的结构。 一个人为的例子（与UCT无关）： 

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

data STRefPair s a b = STRefPair { left :: STRef s a, right :: STRef s b }

mkStRefPair :: a -> b -> ST s (STRefPair s a b)
mkStRefPair a b = do
    a' <- newSTRef a
    b' <- newSTRef b
    return $ STRefPair a' b'

derp :: (Num a, Num b) => STRefPair s a b -> ST s ()
derp p = do
    modifySTRef (left p) (x -> x + 1)
    modifySTRef (right p) (x -> x - 1)

herp :: (Num a, Num b) => (a, b)
herp = runST $ do
    p <- mkStRefPair 0 0
    replicateM_ 10 $ derp p
    a <- readSTRef $ left p
    b <- readSTRef $ right p
    return (a, b)

main = print herp -- should print (10, -10)

很显然，这个特殊的例子在不使用ST情况下编写起来会容易得多，但是希望能够清楚地知道我要去哪里......如果我将这种风格应用到我的UCT用例中，那是错误的吗？

几年前有人问了一个类似的问题，但我认为我的问题有点不同......在适当的时候使用monads封装可变状态是没有问题的，但是它是“适当的时候”从句引起的。 我担心我会过早地回到面向对象的思维模式，在那里我有一堆有getter和setter的对象。 不完全是惯用的Haskell ...

另一方面，如果对某些问题是合理的编码风格，我想我的问题变成：是否有任何知名的方法来保持这种代码的可读性和可维护性？ 我对所有的显式读写都有所了解，尤其是通过必须从ST monad中的基于STRef的结构翻译为外部同构但不可变的结构进行转换。

我不太多使用ST，但有时它只是最好的解决方案。 这可能出现在很多情况下：

  • 已经有众所周知的，有效的方法来解决问题。 Quicksort就是一个很好的例子。 它以其速度和就地行为而闻名，纯代码无法很好地模仿它。
  • 你需要严格的时间和空间界限。 特别是对于懒惰的评估（Haskell甚至没有指定是否有懒惰的评估，只是它不是严格的），你的程序的行为可能是非常不可预测的。 是否存在内存泄漏可能取决于是否启用某种优化。 这与命令式代码有很大不同，命令式代码有一组固定的变量（通常是）和定义的评估顺序。
  • 你有最后期限。 虽然纯粹的风格几乎总是更好的练习和更简洁的代码，但如果你习惯于尽快编写代码并很快需要代码，那么开始执行命令并在以后转向功能是一个非常合理的选择。

    • 当我使用ST（和其他单子）时，我尝试遵循以下一般准则：

  • 经常使用应用风格。 这使得代码更易于阅读，并且如果切换到不可变版本，则转换起来更容易。 不仅如此，应用风格也更加紧凑。
  • 不要只使用ST。 如果你只用ST进行编程，结果将不会比一个巨大的C程序更好，可能更糟的是由于明确的读写。 相反，散布纯Haskell代码应用。 我经常发现自己使用像STRef s (Map k [v]) 。 地图本身正在发生变化，但大部分重要工作都是纯粹完成的。
  • 如果不需要，不要重新制作库。 为IO编写的许多代码可以干净利落地转换为ST。 更换所有IORef与S STRef S和IO s的ST S IN Data.HashTable比写一个手工编码的哈希表的实现将更加容易，而且可能更快了。

    • 最后一个注意事项 - 如果您在显式读取和写入时遇到问题，可以绕过它。

    使用变异和算法的算法不是不同的算法。 有时候，从前者到后者有一个严格的边界保留的翻译，有时是一个困难的翻译，有时只有一个翻译不能保留复杂的边界。

    这篇论文的一个简短的例子告诉我，我认为它不是突变的必要用途 - 所以我认为可以开发一个潜在的非常漂亮的懒惰函数算法。 但它将是一个不同但相关的算法。

    下面，我描述了一种这样的方法 - 不一定是最好或最聪明的，但非常简单：

    以下是我理解的设置 - A）构建分支树B）然后将支付从叶子推回到根，然后在任何给定步骤中指示最佳选择。 但是这样很昂贵，所以相反，只有部分树木以非确定的方式探索叶子。 此外，对树的每一次进一步探索都取决于以前探索中学到的东西。

    所以我们构建代码来描述“stage-wise”树。 然后，我们有另一个数据结构来定义一个部分探索的树以及部分奖励估计值。 然后，我们有一个randseed -> ptree -> ptree的函数，给定一个随机种子和一个部分探索的树，开始进一步探索树，随时更新ptree结构。 然后，我们可以通过在空的种子树上迭代这个函数来获得ptree中越来越多的采样空间列表。 然后，我们可以走这个列表，直到满足某个指定的截止条件。

    所以现在我们已经从一种算法将一切都融合到一起到三个不同的步骤 - 1）懒惰地构建整个状态树，2）用一些结构抽样更新一些局部探索，3）决定我们什么时候开始收集足够的样本。

    当使用ST是合适的时候可能很难分辨出来。 我建议你用ST和ST来做（不一定按顺序）。 保持非ST版本简单; 使用ST应该被看作是一种优化，在你知道需要它之前你不想这样做。

    链接地址: http://www.djcxy.com/p/80869.html

    上一篇: ST Monad == code smell?

    下一篇: Resources for working with Machine Learning in F#