ST Monad == Кодовый запах?

Question

Я работаю над реализацией алгоритма UCT в Haskell, который требует значительного объема данных.Не вдаваясь в подробности, это алгоритм моделирования, в котором на каждом «шаге» выбирается листовой узел в дереве поиска на основе некоторых статистических свойств, на этом листе создается новый дочерний узел, а статистика соответствуетобновлен новый лист и все его предки.

Учитывая все это жонглирование, я не настолько умен, чтобы выяснить, как сделать все дерево поиска хорошей неизменной структурой данных - la Okasaki .Вместо этого я немного поигрался с монадой ST, создавая структуры, состоящие из изменяемых STRef s.Придуманный пример (не связанный с 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 в изоморфные, но неизменные структуры снаружи.

Answer 1

Я не очень часто использую ST, но иногда это просто лучшее решение. Это может быть во многих сценариях:

• Уже существуют хорошо известные эффективные способы решения проблемы. Quicksort является прекрасным примером этого. Он известен своей скоростью и поведением на месте, которое не очень хорошо подражает чистому коду.
• Вам нужны жесткие ограничения времени и пространства. Особенно с ленивой оценкой (а Haskell даже не указывает, есть ли ленивая оценка, только потому, что она не строгая), поведение ваших программ может быть очень непредсказуемым. Наличие утечки памяти может зависеть от того, включена ли определенная оптимизация. Это очень отличается от императивного кода, который имеет фиксированный набор переменных (обычно) и определенный порядок оценки.
• У вас есть крайний срок. Хотя чистый стиль - это почти всегда лучшая практика и более чистый код, если вы привыкли к обязательному написанию и скоро нуждаетесь в коде, начинать с императива и переходить к функционалу позже - вполне разумный выбор.

Когда я использую ST (и другие монады), я стараюсь следовать этим общим правилам:

• Используйте Аппликативный стиль часто. Это облегчает чтение кода и, если вы переключаетесь на неизменяемую версию, намного проще конвертировать. Мало того, но стиль Applicative гораздо компактнее.
• Не просто используйте ST. Если вы программируете только на ST, результат будет не лучше, чем у огромной программы на C, возможно, хуже из-за явного чтения и записи. Вместо этого перемежайте чистый код на Haskell, где он применяется. Я часто использую такие вещи, как STRef s (Map k [v]). Сама карта видоизменяется, но большая часть тяжелой работы выполняется чисто.
• Не переделывать библиотеки, если не нужно. Большая часть кода, написанного для ввода-вывода, может быть чисто и довольно механически преобразована в ST. Замена всех IORef s на STRef s и IO s на ST s в Data.HashTable была намного проще, чем была бы написана реализация хеш-таблицы с ручным кодированием, и, вероятно, также быстрее.

Последнее замечание: если у вас возникают проблемы с явным чтением и записью, есть способов обойти это .

Answer 2

Алгоритмы, которые используют мутации и алгоритмы, которые не являются разными алгоритмами.Иногда есть прямой и сохраняющий границы перевод с первого на второе, иногда трудный, а иногда только тот, который не сохраняет границ сложности.

Снимок статьи показывает мне, что я неЯ думаю, что он существенно использует мутацию - и поэтому я думаю, что потенциально очень изящный ленивый функциональный алгоритм может быть разработан.Но это был бы другой, но связанный алгоритм с описанным.

Ниже я опишу один такой подход - не обязательно лучший или самый умный, но довольно простой:

Вот установкаЯ понимаю это - A) ветвящееся дерево строится B) выигрыши затем отодвигаются от листьев к корню, что затем указывает на лучший выбор на любом данном этапе. Но это дорого, поэтому вместо этого только листья дерева исследуются на листьях недетерминированным образом.Кроме того, каждое дальнейшее исследование дерева определяется тем, что было изучено в предыдущих исследованиях.

Поэтому мы создаем код для описания «поэтапного» дерева.Затем у нас есть другая структура данных для определения частично изученного дерева вместе с частичными оценками вознаграждения.Затем у нас есть функция randseed -> ptree -> ptree, которая дает случайное начальное число и частично исследованное дерево, приступает к одному дальнейшему исследованию дерева, обновляя структуру ptree по мере продвижения.Затем мы можем просто перебрать эту функцию по пустому начальному дереву, чтобы получить список все более и более пробельных пространств в этом дереве.Затем мы можем пройти этот список до тех пор, пока не будет выполнено определенное условие обрезания.

Итак, теперь мы перешли от одного алгоритма, в котором все смешано, к трем отдельным шагам - 1) лениво построим все дерево состояний,2) обновить некоторые частичные исследования с некоторыми выборками структуры и 3) решить, когда мы собрали достаточно образцов.

Answer 3

Может быть действительно трудно сказать, когда использование ST подходит. Я бы посоветовал вам сделать это с ST и без ST (не обязательно в таком порядке). Держите не-ST версию простой; использование ST следует рассматривать как оптимизацию, и вы не хотите этого делать, пока не поймете, что вам это нужно.

Answer 4

Использование монады ST обычно (но не всегда) в качестве оптимизации.Для любой оптимизации я применяю ту же процедуру:

1. Пишем код без него,
2. Профилируем и выявляем узкие места,
3. Постепенно переписываем узкие места и проверяем на улучшения/ regressions,

Другой известный мне вариант использования - это альтернатива государственной монаде.Ключевым отличием является то, что в монаде состояния тип всех хранимых данных указывается сверху вниз, а в монаде ST - снизу вверх.Есть случаи, когда это полезно.

Answer 5

Я должен признать, что не могу прочитать код на Haskell. Но если вы используете ST для изменения дерева, вы, вероятно, можете заменить его неизменным деревом, не теряя много, потому что:

Та же сложность для изменчивого и неизменного дерева

Вы должны мутировать каждый узел над новым листом. Неизменяемое дерево должно заменить все узлы над измененным узлом. Таким образом, в обоих случаях затронутые узлы одинаковы, поэтому вы ничего не получите по сложности.

Например, Создание Java-объекта обходится дороже, чем мутация, поэтому, возможно, вы можете немного выиграть в Haskell, используя мутацию Но этого я точно не знаю. Но небольшой выигрыш не принесет вам особой выгоды из-за следующего пункта.

Обновление дерева, по-видимому, не является узким местом

Оценка нового листа, вероятно, будет намного дороже, чем обновление дерева. По крайней мере, так обстоит дело с UCT в компьютере Go.