haskell - ST Monad == 代码味道？

Question

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

考虑到所有这些杂耍，我还不够敏锐，无法弄清楚如何使整个搜索树成为一个很好的不可变数据结构Okasaki 。相反，我一直在尝试使用 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用例，这是错误的吗？

有人问similar question几年前，但我认为我的问题有点不同......我在适当的时候使用 monad 来封装可变状态没有问题，但正是“适当的时候”子句让我着迷。我担心我过早地恢复到面向对象的思维方式，其中我有一堆带有 getter 和 setter 的对象。不完全是惯用的 Haskell...

另一方面，如果它是解决某些问题的合理编码风格，我想我的问题就变成:是否有任何众所周知的方法来保持此类代码的可读性和可维护性？我对所有显式读取和写入感到有点恶心，尤其是因为必须将 ST monad 内基于 STRef 的结构转换为同构，但外部不可变的结构。

Answer 1

我不太使用ST，但有时它只是最好的解决方案。这可以在很多场景中实现:

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

当我使用 ST(和其他 monad)时，我尝试遵循以下一般准则:

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

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