ST Monad == Кодовый запах?
Я работаю над реализацией алгоритма UCT в Haskell, который требует значительного объема данных. Не вдаваясь в подробности, это алгоритм моделирования, в котором на каждом "шаге" выбирается листовой узел в дереве поиска на основе некоторых статистических свойств, на этом листе строится новый дочерний узел, а статистика соответствует новый лист и все его предки обновляются.
Учитывая все это жонглирование, я не достаточно умен, чтобы понять, как сделать все дерево поиска хорошей неизменной структурой данных в стиле Окасаки. Вместо этого я играл с 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, это неправильно?
Кто-то задавал подобный вопрос здесь пару лет назад, но я думаю, что мой вопрос немного отличается... У меня нет проблем с использованием монад для инкапсуляции изменяемого состояния, когда это уместно, но это то, что "когда уместно", вызывает меня. Я беспокоюсь, что преждевременно возвращаюсь к объектно-ориентированному мышлению, где у меня есть куча объектов с геттерами и сеттерами. Не совсем идиоматичный Хаскелл...
С другой стороны, если это разумный стиль кодирования для некоторого набора проблем, я предполагаю, что у меня возникает вопрос: существуют ли какие-либо хорошо известные способы сделать этот вид кода читабельным и обслуживаемым? Я отчасти отвержен всеми явными операциями чтения и записи, и особенно оттого, что мне приходится переводить с моего STRef на основе структур внутри ST монадой к изоморфным, но неизменным структурам снаружи.
5 ответов
Я не очень часто использую ST, но иногда это просто лучшее решение. Это может быть во многих сценариях:
- Уже есть известные, эффективные способы решения проблемы. Quicksort является прекрасным примером этого. Он известен своей скоростью и поведением на месте, которое не очень хорошо подражает чистому коду.
- Вам нужны жесткие ограничения времени и пространства. Особенно с ленивой оценкой (а Haskell даже не указывает, есть ли ленивая оценка, только потому, что она не строгая), поведение ваших программ может быть очень непредсказуемым. Наличие утечки памяти может зависеть от того, включена ли определенная оптимизация. Это очень отличается от императивного кода, который имеет фиксированный набор переменных (обычно) и определенный порядок оценки.
- У вас есть крайний срок. Хотя чистый стиль почти всегда лучше практики и более чистый код, если вы привыкли писать императивно и скоро нуждаетесь в коде, начинать с императива и переходить к функционалу позже - вполне разумный выбор.
Когда я использую ST (и другие монады), я стараюсь следовать этим общим правилам:
- Используйте Аппликативный стиль часто. Это делает код более легким для чтения и, если вы переключаетесь на неизменяемую версию, намного легче конвертировать. Мало того, но стиль Applicative гораздо компактнее.
- Не просто используйте ST. Если вы программируете только на ST, результат будет не лучше, чем у огромной программы на C, возможно, хуже из-за явного чтения и записи. Вместо этого перемежайте чистый код на Haskell, где он применяется. Я часто использую такие вещи, как
STRef s (Map k [v]), Сама карта видоизменяется, но большая часть тяжелой работы выполняется чисто. - Не переделывать библиотеки, если вам не нужно. Большая часть кода, написанного для IO, может быть чисто и довольно механически преобразована в ST. Замена всех
IORefсSTRefс иIOсSTs в Data.HashTable было намного проще, чем была бы написана реализация хеш-таблицы с ручным кодированием, и, вероятно, также быстрее.
Последнее замечание - если у вас возникают проблемы с явным чтением и записью, есть способы обойти это.
Алгоритмы, которые используют мутации и алгоритмы, которые не являются разными алгоритмами. Иногда существует прямой перевод, сохраняющий границы, от первого к последнему, иногда трудный, а иногда только тот, который не сохраняет границ сложности.
Небольшая часть статьи показывает мне, что я не думаю, что она существенно использует мутацию, и поэтому я думаю, что потенциально действительно изящный ленивый функциональный алгоритм может быть разработан. Но это будет другой, но связанный алгоритм с описанным.
Ниже я опишу один такой подход - не обязательно лучший или самый умный, но довольно простой:
Вот настройка, я понимаю это - A) ветвящееся дерево строится B) выигрыши затем отодвигаются от листьев к корню, что затем указывает на лучший выбор на любом данном этапе. Но это дорого, поэтому вместо этого только части дерева исследуются на листьях недетерминированным образом. Кроме того, каждое дальнейшее исследование дерева определяется тем, что было изучено в предыдущих исследованиях.
Поэтому мы строим код для описания "поэтапного" дерева. Затем у нас есть другая структура данных для определения частично изученного дерева вместе с частичными оценками вознаграждения. Тогда у нас есть функция randseed -> ptree -> ptree это дает случайное семя и частично изученное дерево, и мы приступаем к еще одному исследованию дерева, обновляя структуру дерева в процессе работы. Затем мы можем просто перебрать эту функцию по пустому начальному дереву, чтобы получить список все более и более сэмплированных пробелов в этом дереве. Затем мы можем пройти этот список, пока не будет выполнено определенное условие отсечения.
Итак, теперь мы перешли от одного алгоритма, где все смешано вместе, к трем отдельным шагам: 1) построение всего дерева состояний, лениво, 2) обновление некоторого частичного исследования с некоторой выборкой структуры и 3) принятие решения, когда мы собрал достаточно образцов.
Это может быть действительно трудно сказать, когда использование ST целесообразно. Я бы посоветовал вам сделать это с ST и без ST (не обязательно в таком порядке). Сохраняйте простую версию без ST; использование ST следует рассматривать как оптимизацию, и вы не захотите этого делать, пока не поймете, что вам это нужно.
Я должен признать, что не могу прочитать код на Haskell. Но если вы используете ST для изменения дерева, вы, вероятно, можете заменить его неизменным деревом, не теряя много, потому что:
Та же сложность для изменчивого и неизменного дерева
Вы должны мутировать каждый узел над новым листом. Неизменяемое дерево должно заменить все узлы над измененным узлом. Таким образом, в обоих случаях затронутые узлы одинаковы, таким образом, вы ничего не получите по сложности.
Например, создание объектов Java обходится дороже, чем мутация, поэтому, возможно, вы можете получить немного здесь, в Хаскеле, используя мутацию. Но этого я точно не знаю. Но небольшой выигрыш не принесет вам особой выгоды из-за следующего пункта.
Обновление дерева, по-видимому, не является узким местом
Оценка нового листа, вероятно, будет намного дороже, чем обновление дерева. По крайней мере, так обстоит дело с UCT в компьютере Go.
Использование монады ST обычно (но не всегда) в качестве оптимизации. Для любой оптимизации я применяю ту же процедуру:
- Напишите код без него,
- Профилировать и определять узкие места,
- Постепенно переписывать узкие места и проверять улучшения / регрессии,
Другой известный мне вариант использования - это альтернатива государственной монаде. Основное отличие состоит в том, что в монаде состояния тип всех хранимых данных указывается сверху вниз, тогда как в монаде ST он задается снизу вверх. Есть случаи, когда это полезно.