ST Monad ==代码味道？ [英] ST Monad == code smell?

问题描述

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

鉴于所有这些杂耍，我没有足够的锐利去弄清楚如何让整个搜索树成为一个不可变的数据结构la Okasaki 。相反，我一直在玩 ST monad，创建由可变 STRef s组成的结构。一个人为的例子（与UCT无关）：

import Control.Monad
import Control .Monad.ST
导入Data.STRef

数据STRefPair sab = STRefPair {left :: STRef sa，right :: STRef sb}

mkStRefPair :: a - > b - > ST s（STRefPair sab）
mkStRefPair ab = do
a'< - newSTRef a
b'< - newSTRef b
return $ STRefPair a'b'

derp ::（数字a，数字b）=> STRefPair s a b - > ST s（）
derp p = do
modifySTRef（left p）（\ x - > x + 1）
modifySTRef（right p）（\ x - > x - 1）

herp ::（数字a，数字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用例，那是错误的？

有人问a 类似的问题在几年前，但我想我的问题有点儿不同......我没有问题，使用monads在适当的时候封装可变状态，但它是适当时的条款，让我。我担心我会过早地回到面向对象的思维模式，在那里我有一堆有getter和setter的对象。另一方面，如果对某些问题是一种合理的编码风格，我想我的问题变成：是否有任何知名的方法来保持这种代码的可读性和可维护性？我对所有的显式读写都有所了解，特别是在我的基于STRef 的结构中翻译

解决方案

我不多使用ST，但是ST monad对于同构但是不可变的结构。有时候这只是最好的解决方案。这可以在很多情况下：

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


• 您需要严格的时间和空间界限。特别是对于懒惰的评估（Haskell甚至没有指定是否有懒惰的评估，只是它不是严格的），你的程序的行为可能是非常不可预测的。是否存在内存泄漏可能取决于是否启用某种优化。这与命令式代码有很大的不同，命令式代码有一组固定的变量（通常是）和定义的评估顺序。 你有一个截止日期。尽管纯风格几乎总是更好的练习和更简洁的代码，但如果您习惯于尽快编写代码并很快需要代码，那么开始执行命令并在稍后转向功能是一个非常合理的选择。

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

• 经常使用应用风格。这使得代码更易于阅读，并且如果切换到不可变版本，则转换起来更容易。不仅如此，应用风格也更为紧凑。
  
• 不要仅仅使用ST。如果你只用ST进行编程，结果将不会比一个巨大的C程序更好，可能更糟的是由于明确的读写。相反，散布纯Haskell代码应用。我经常发现自己使用的东西像 STRef（Map k [v]）。地图本身正在发生变化，但大部分繁重工作都是纯粹完成的。


• 如果不需要，不要重新制作库。为IO编写的许多代码可以干净利落地转换为ST。用 STRef s和 IO s替换所有 IORef 在Data.HashTable中使用 ST s要比编写一个手工编码的哈希表实现更容易，而且可能也更快。

最后一个注意事项 - 如果您在显式读取和写入时遇到问题，那么围绕它的方式。

I'm working on implementing the UCT algorithm in Haskell, which requires a fair amount of data juggling. Without getting into too much detail, it's a simulation algorithm where, at each "step," a leaf node in the search tree is selected based on some statistical properties, a new child node is constructed at that leaf, and the stats corresponding to the new leaf and all of its ancestors are updated.

Given all that juggling, I'm not really sharp enough to figure out how to make the whole search tree a nice immutable data structure à la Okasaki. Instead, I've been playing around with the ST monad a bit, creating structures composed of mutable STRefs. A contrived example (unrelated to 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)

Obviously this particular example would be much easier to write without using ST, but hopefully it's clear where I'm going with this... if I were to apply this sort of style to my UCT use case, is that wrong-headed?

Somebody asked a similar question here a couple years back, but I think my question is a bit different... I have no problem using monads to encapsulate mutable state when appropriate, but it's that "when appropriate" clause that gets me. I'm worried that I'm reverting to an object-oriented mindset prematurely, where I have a bunch of objects with getters and setters. Not exactly idiomatic Haskell...

On the other hand, if it is a reasonable coding style for some set of problems, I guess my question becomes: are there any well-known ways to keep this kind of code readable and maintainable? I'm sort of grossed out by all the explicit reads and writes, and especially grossed out by having to translate from my STRef-based structures inside the ST monad to isomorphic but immutable structures outside.

解决方案

I don't use ST much, but sometimes it is just the best solution. This can be in many scenarios:

• There are already well-known, efficient ways to solve a problem. Quicksort is a perfect example of this. It is known for its speed and in-place behavior, which cannot be imitated by pure code very well.
• You need rigid time and space bounds. Especially with lazy evaluation (and Haskell doesn't even specify whether there is lazy evaluation, just that it is non-strict), the behavior of your programs can be very unpredictable. Whether there is a memory leak could depend on whether a certain optimization is enabled. This is very different from imperative code, which has a fixed set of variables (usually) and defined evaluation order.
• You've got a deadline. Although the pure style is almost always better practice and cleaner code, if you are used to writing imperatively and need the code soon, starting imperative and moving to functional later is a perfectly reasonable choice.

When I do use ST (and other monads), I try to follow these general guidelines:

• Use Applicative style often. This makes the code easier to read and, if you do switch to an immutable version, much easier to convert. Not only that, but Applicative style is much more compact.
• Don't just use ST. If you program only in ST, the result will be no better than a huge C program, possibly worse because of the explicit reads and writes. Instead, intersperse pure Haskell code where it applies. I often find myself using things like STRef s (Map k [v]). The map itself is being mutated, but much of the heavy lifting is done purely.
• Don't remake libraries if you don't have to. A lot of code written for IO can be cleanly, and fairly mechanically, converted to ST. Replacing all the IORefs with STRefs and IOs with STs in Data.HashTable was much easier than writing a hand-coded hash table implementation would have been, and probably faster too.

One last note - if you are having trouble with the explicit reads and writes, there are ways around it.

这篇关于ST Monad ==代码味道？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！