Я работаю над реализацией алгоритма UCT в Haskell , который требует большого количества манипуляций с данными. Не вдаваясь в подробности, это алгоритм моделирования, в котором на каждом «шаге» листовой узел в дереве поиска выбирается на основе некоторых статистических свойств, на этом листе создается новый дочерний узел, а статистика соответствует новый лист и все его предки обновляются.
Учитывая все это жонглирование, я недостаточно сообразителен, чтобы понять, как сделать все дерево поиска красивой неизменной структурой данных а-ля Окасаки. Вместо этого я немного поигрался с монадой ST
, создав структуры, состоящие из изменяемых 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, это неправильно?
Кто-то задал аналогичный вопрос здесь пару лет назад, но Я думаю, что мой вопрос немного другой ... У меня нет проблем с использованием монад для инкапсуляции изменяемого состояния, когда это необходимо, но меня привлекает именно предложение «когда необходимо». Меня беспокоит, что я преждевременно возвращаюсь к объектно-ориентированному мышлению, когда у меня есть куча объектов с геттерами и сеттерами. Не совсем идиоматический Haskell ...
С другой стороны, если это разумный стиль кодирования для некоторого набора проблем, я предполагаю, что у меня будет вопрос: есть ли какие-нибудь известные способы сделать такой код читабельным и поддерживаемым? Я как бы выброшен из-за всех явных операций чтения и записи, и особенно из-за того, что мне пришлось переводить из моих STRef
-основанных структур внутри ST
монады в изоморфные, но неизменяемые структуры снаружи.
time ∩ budget
- person Thomas Eding   schedule 25.10.2011liftM2
:mkStRefPair a b = liftM2 STRefPair (newSTRef a) (newSTRef b)
,liftM2 (,) (readSTRef $ left p) (readSTRef $ right p)
- person sdcvvc   schedule 25.10.2011liftM2
в конструкторах данных. - person mergeconflict   schedule 25.10.2011ST
, когда вам нужна мутация, и вам нужна мутация, когда алгоритм требует мутации для сохранения границ сложности и принятия решения если алгоритм нуждается в изменении для сохранения границ сложности путем анализа алгоритма. - person sclv   schedule 27.10.2011