首页 文章

ST Monad ==代码味道？

提问于
浏览 次
45

我正在努力在Haskell中实现UCT算法，这需要大量的数据杂耍 . 在没有深入细节的情况下，它是一种模拟算法，其中，在每个"step,"搜索树中的叶节点基于某些统计属性被选择，在该叶子处构造新的子节点，并且对应于新叶子和它的所有祖先都会更新 .

鉴于所有这些杂耍，我并不是非常敏锐，无法弄清楚如何使整个搜索树成为一个不错的不可变数据结构 . 相反，我一直在玩 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 的情况下写起来会容易得多，但希望's clear where I'这样做...如果我将这种风格应用到我的UCT用例中，那是错误的吗？

几年前有人问过similar question，但我认为我的问题有点不同......我在使用monads时可以在适当的时候封装可变状态，但是我担心我会回归到面向对象的问题 . 过早的心态，我有一堆带有吸气剂和制定者的物体 . 不完全是惯用的Haskell ......

另一方面，如果对于某些问题来说它是一种合理的编码风格，我想我的问题就变成了：有没有任何众所周知的方法来保持这种代码的可读性和可维护性？我有点被所有明确的读写所淹没，特别是通过从 ST monad中的基于 STRef 的结构转换为外部的同构但不可变的结构而得到满足 .

haskell state monads state-monad

5 回答

  • 2

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

    • 已经有众所周知的有效方法来解决问题 . Quicksort就是一个很好的例子 . 它以其速度和就地行为而闻名，不能很好地模仿纯粹的代码 .

    • 您需要严格的时间和空间限制 . 特别是对于懒惰的评估（并且Haskell甚至没有指定是否存在惰性评估，只是它是非严格的），程序的行为可能非常难以预测 . 是否存在内存泄漏可能取决于是否启用了某个优化 . 这与命令式代码非常不同，命令式代码具有固定的变量集（通常）和定义的评估顺序 .

    • 你有一个截止日期 . 虽然纯粹的风格几乎总是更好的练习和更清晰的代码，但如果你习惯于强制写作并且很快就需要代码，那么启动命令并稍后转向功能是一个非常合理的选择 .

    当我使用ST（和其他monad）时，我尝试遵循这些一般准则：

    • 经常使用Applicative样式 . 这使代码更容易阅读，如果你切换到不可变版本，更容易转换 . 不仅如此，应用风格更加紧凑 .

    • 不要只使用ST . 如果你只在ST中编程，结果将不会比一个巨大的C程序更好，可能因为显式读写而更糟 . 相反，它适用于散布的纯Haskell代码 . 我经常发现自己使用像 STRef s (Map k [v]) 这样的东西 . Map 本身正在发生变异，但很多繁重的工作都是纯粹的 .

    • 唐't remake libraries if you don' t必须 . 为IO编写的许多代码可以干净利落，并且相当机械地转换为ST . 用Data.HashTable中的 ST 替换 STRef 和 IO 的所有 IORef s比编写手工编码的哈希表实现要容易得多，而且可能更快 .

    最后一点 - 如果您在显式读写方面遇到问题，则有ways around it .

    回复于
  • 11

    利用变异和算法的算法不是不同的算法 . 有时候，从前者到后者的翻译有一个明确的边界保留，有时是困难的翻译，有时只有一个不能保留复杂性的边界 .

    本文的一篇文章向我揭示了我并不认为它突然变得必不可少 - 因此我认为可以开发一种潜在的非常漂亮的懒惰函数算法 . 但它与描述的不同但是相关的算法 .

    下面，我描述了一种这样的方法 - 不一定是最好或最聪明，但很漂亮直截了当：

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

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

    所以现在我们已经从一个算法混合到三个不同的步骤 - 1） Build 整个状态树，懒洋洋地，2）用一些结构的样本更新一些部分探索和3）决定我们什么时候收集了足够的样本

    回复于
  • 2

    使用ST是合适的，这真的很难说 . 我建议你用ST而不用ST（不一定按顺序） . 保持非ST版本简单;使用ST应该被看作是一种优化，在你知道需要它之前你不想这样做 .

    回复于
  • 40

    我不得不承认我无法读取Haskell代码 . 但是如果你使用ST来改变树，那么你可以用一个不可变的树替换它而不会丢失很多，因为：

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

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

    对于例如Java对象创建比变异更昂贵，所以也许你可以通过使用变异在Haskell中获得一些 . 但我不确定这一点 . 但是，由于下一点，小幅上涨不会给你带来太大的收益 .

    更新树可能不是瓶颈

    对新叶的评估可能比更新树要昂贵得多 . 至少在计算机Go的UCT就是这种情况 .

    回复于
  • 9

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

    • 没有它编写代码，

    • 简介并识别瓶颈，

    • 逐步重写瓶颈并测试改进/回归，

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

    回复于

相关问题