ST Monad == запах кода?

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

Учитывая все то, что жонглирование, я не настолько острый, чтобы понять, как сделать все дерево поиска хорошей неизменной структурой данных à 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, это заблуждающимся?

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

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

Ответ 1

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

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

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

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

Одна последняя заметка - если у вас возникли проблемы с явным чтением и записью, существуют способы вокруг нее.

Ответ 2

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

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

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

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

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

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

Ответ 3

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

Ответ 4

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

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

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

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

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

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

Ответ 5

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

Введите код без него,
Профиль и выявить узкие места,
Интенсивно переписывайте узкие места и проверяйте улучшения/регрессии,

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