Как мне объединить монаду St и монаду State (или эквивалент)?

Я создаю код, чтобы понять, на самом деле решатель пасьянса. У меня есть простая реализация грубой силы, которая использует монаду состояния, на самом деле просто чтобы доказать, что я могу ее использовать (она только ведет счет каждого оцененного хода). Но теперь я хочу использовать неупакованные изменяемые массивы для записи посещенных досок и, таким образом, быстрой оценки путей, когда я достигаю позиции платы, которая уже была посещена по другому пути. Кажется, что монада ST не позволяет мне распределять неявное состояние, но я должен использовать ST (или IO), чтобы получить доступ к изменяемому массиву. Итак, кажется, я должен объединить две монады - State, чтобы распределять состояние (которое фактически будет включать в себя изменяемый массив), и еще одну (ST), чтобы получить функции изменяемого массива.

  • Это правильно?
  • И если да, то есть ли лучшая альтернатива, чем (каноническая?) Комбинация Data.Array.ST/Control.Monad.ST/Control.Monad.ST и mtl?
  • Если я пойду по этому пути, имеет ли значение, в каком порядке я складываю ST и State?
  • Следует ли мне рассмотреть возможность создания моей собственной монады, основанной на одном или обоих ST или State, чтобы избежать использования преобразователей монад?

arrays mutable haskell state-monad monad-transformers
person hdb3    schedule 20.02.2014    source источник

Ответы (2)


arrow_upward
5
arrow_downward

Я не уверен на 100%, что монада ST - это способ повысить производительность такой поисковой задачи. Но если предположить, что это ... Вы можете "состояние потока", просто поместив состояние, которое вы хотите сохранить, в STRef. Вы можете сделать это без необходимости смешивать несколько монад вместе, что должно значительно упростить вам задачу.

Вам определенно понадобится монада ST или IO, если вы хотите изменяемое состояние. (Или монада STM, но она используется только для синхронизации потоков, которая здесь вам не нужна.)

Порядок расположения монад может иметь значение, но в данном случае это не так. Если у вас есть что-то вроде монады List и монады Error, то, в зависимости от порядка наложения, ошибка либо не соответствует только одной возможности в списке, либо всем возможностям в списке. В вашем случае нет никаких эффектов, которые меняются в зависимости от порядка стека.

... что хорошо, поскольку нет преобразователя для превращения вещей в ST. Итак, ST должен быть внутренней монадой.

Сказав все это, я снова не думаю, что вам действительно нужен стек монад. Думаю, подойдет простой STRef.

person MathematicalOrchid    schedule 20.02.2014
comment
Если я пойду по этому пути, как я могу передать переменную состояния (которая включает изменяемый массив)? Когда я прочитал ваше предложение, я бы создал STRef во главе моей рекурсивной функции и явно прочитал и записал его, гарантируя, что STRef всегда виден в функциях, определенных в функции верхнего уровня? В отличие от использования State, где оно неявно, когда я использую монадическое связывание, могу ли я добиться того же только в ST? Если да, то как? - person hdb3; 21.02.2014
comment
Вы можете определить type STState s st = ReaderT (STRef s st) (ST s), а затем запустить STState вычисления через runSTState sts = newSTRef initState >>= runReaderT sts. Этот подход изоморфен простой передаче STRef вручную, но, возможно, более эстетичен. Конечно, в этот момент вам может быть лучше просто использовать StateT st (ST s). - person John L; 21.02.2014
comment
AFAIK, STM используется, чтобы избежать любой синхронизации потоков. - person user3974391; 21.02.2014

arrow_upward
5
arrow_downward

При использовании ST любые массивы или ссылки, которые у вас есть, на самом деле не являются состоянием в State монадном смысле этого слова: они никогда не изменяются! Вы можете думать о них как о указателе; указатель постоянен, хотя то, на что он указывает, может измениться. Таким образом, вы можете просто передавать свои массивы или ссылки или что-то еще в свои ST действия в качестве аргументов функции. Механизм StateT был бы уместен, если вы ожидали, что действие ST должно вернуть другой массив, чем тот, который он был передан, то есть не просто изменить существующий массив, но создать новый. Поскольку это обычно не так, StateT не подходит.

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

person Daniel Wagner    schedule 20.02.2014
comment
Массив не будет «свежим» - возможно, он будет обновлен в одном элементе, и старая версия больше не нужна. Я не понимаю, как ReaderT поможет, так как я хочу обновлять состояние по ходу ... - person hdb3; 21.02.2014
comment
@ hdb3 Я пытаюсь сказать, что вы ошибаетесь. Обновление одного элемента массива не создает новый массив - указатель тот же, только содержимое за указателем отличается! У вас нет состояния для обновления. Все указатели остаются прежними. - person Daniel Wagner; 21.02.2014