47

我正在努力在 Haskell 中实现UCT算法，这需要大量的数据处理。无需过多详细介绍，它是一种模拟算法，在每个“步骤”中，根据一些统计属性选择搜索树中的一个叶节点，在该叶上构造一个新的子节点，并对应于新叶子及其所有祖先都已更新。

考虑到所有这些杂耍，我还不够敏锐，无法弄清楚如何使整个搜索树成为一个不错的不可变数据结构 à la Okasaki。相反，我一直在玩弄STmonad，创建由 mutable 组成的结构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 用例，那是不是走错路了？

几年前有人在这里问过类似的问题，但我认为我的问题有点不同......我在适当的时候使用 monad 封装可变状态没有问题，但正是“适当的时候”子句让我着迷。我担心我会过早地回到面向对象的心态，我有一堆带有 getter 和 setter 的对象。不完全是惯用的 Haskell ......

另一方面，如果它对于某些问题来说是一种合理的编码风格，我想我的问题就变成了：是否有任何众所周知的方法来保持这种代码的可读性和可维护性？我对所有显式的读取和写入感到有点恶心，尤其是不得不从monadSTRef内部的基于 my 的结构转换为ST外部的同构但不可变的结构。

4

5 回答 5

42

我用 ST 不多，但有时它只是最好的解决方案。这可以在许多情况下：

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

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

  • 经常使用Applicative风格。这使代码更易于阅读，并且如果您确实切换到不可变版本，则更容易转换。不仅如此，Applicative 风格更加紧凑。
  • 不要只使用 ST。如果你只在 ST 中编程，结果不会比一个巨大的 C 程序好，因为显式读写可能更糟。相反，在适用的地方散布纯 Haskell 代码。我经常发现自己使用诸如STRef s (Map k [v]). 地图本身正在发生变化，但大部分繁重的工作都是纯粹完成的。
  • 如果不需要，请不要重新制作库。为 IO 编写的许多代码可以干净且相当机械地转换为 ST。IORef在 Data.HashTable中用STRefs 和IOs替换所有sST比编写手动编码的哈希表实现要容易得多，而且可能更快。

最后一点 - 如果您在显式读取和写入方面遇到问题，有办法解决它。

于 2011-11-01T00:52:58.967 回答
11

利用变异的算法和不使用变异的算法是不同的算法。有时存在从前者到后者的直截了当的保界转换，有时是困难的转换，有时只有不保持复杂性界限的转换。

浏览一下这篇论文告诉我，我认为它没有必要使用突变——因此我认为可以开发一种可能非常漂亮的惰性函数算法。但这将是与所描述的算法不同但相关的算法。

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

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

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

所以现在我们已经从一个所有东西都混合在一起的算法变成了三个不同的步骤——1）懒惰地构建整个状态树，2）用结构的一些采样更新一些部分探索，3）决定我们什么时候已经收集了足够的样本。

于 2011-10-25T17:43:35.367 回答
9

很难判断何时使用 ST 合适。我建议您使用 ST 和不使用 ST（不一定按此顺序）。保持非 ST 版本简单；使用 ST 应该被视为一种优化，在您知道自己需要它之前，您不想这样做。

于 2011-10-24T20:58:50.890 回答
2

我不得不承认我无法阅读 Haskell 代码。但是如果你使用 ST 来改变树，那么你可以用不可变的树替换它而不会损失太多，因为：

可变树和不可变树的复杂度相同

您必须改变新叶子上方的每个节点。不可变树必须替换修改节点上方的所有节点。因此，在这两种情况下，触摸的节点都是相同的，因此您不会获得任何复杂性。

例如，Java 对象创建比突变更昂贵，所以也许你可以通过使用突变在 Haskell 中获得一点。但这我不确定。但是由于下一点，小额收益不会给您带来太多收益。

更新树大概不是瓶颈

新叶子的评估可能会比更新树更昂贵。至少计算机围棋中的 UCT 是这种情况。

于 2011-11-18T13:24:08.373 回答
2

ST monad 的使用通常（但不总是）作为一种优化。对于任何优化，我应用相同的过程：

  1. 不用它写代码，
  2. 剖析和识别瓶颈，
  3. 逐步重写瓶颈并测试改进/回归，

我知道的另一个用例是作为 state monad 的替代方案。关键区别在于，对于 state monad，存储的所有数据的类型是以自上而下的方式指定的，而对于 ST monad，它是自下而上的。在某些情况下，这很有用。

于 2011-11-25T08:52:14.850 回答