Объедините монады ST и List в Haskell

С использованием StateT монаду трансформер, могу создать тип StateT s [] a, который изоморфен s -> [(a, s)], Теперь я бы предпочел использовать STTвместо этого монадный преобразователь, поскольку я хотел бы иметь несколько изменяемых переменных разных типов и хотел бы иметь возможность создавать их экземпляры по своему усмотрению, в зависимости от результатов предыдущих вычислений.

Тем не менее, связанная документация для STT прямо упоминается:

Этот преобразователь монад не следует использовать с монадами, которые могут содержать несколько ответов, например, монадой списка. Причина в том, что токен состояния будет дублироваться в разных ответах, что приведет к возникновению плохих вещей (таких как потеря ссылочной прозрачности). К безопасным монадам относятся монады State, Reader, Writer, Maybe и комбинации соответствующих им монадных трансформаторов.

Так какие у меня варианты?

Чтобы быть полностью ясным:

  • То, что я после, это недетерминизм. Я хочу быть в состоянии раскрутить мои вычисления, давая каждой ветви свою собственную копию всего состояния.
  • Я не особо против параллелизма, так как производительность не является моей главной заботой.
  • Мне не нужен параллелизм: разные ветви вычислений не должны иметь общие переменные; скорее, все они должны работать со своей собственной копией исходной изменяемой переменной.

РЕДАКТИРОВАТЬ: я пришел к выводу, что STT монадный трансформатор, который ведет себя по линии StateT по своей сути небезопасно. С его помощью мы могли бы построить тип STT sloc (ListT (ST sglob)) a, Вот, sglob это имя глобального состояния, в то время как sloc является именем локального состояния.* Теперь мы можем использовать глобальное состояние для обмена ссылками на локальные состояния между потоками, таким образом, потенциально получая ссылки на неинициализированные переменные.

* Для сравнения, соответствующий StateT строительство StateT sloc (ListT (State sglob)) a, который изоморфен sloc -> sglob -> ([(a, sloc)], sglob),

Источник

2 ответа

Решение

Ты не обойдешься StateTпотому что для этого недетерминированного компилятора всегда нужно знать, какие "переменные" нужно разветвить. Это невозможно, когда переменные могут быть где угодно STRefs.

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

{-# LANGUAGE TemplateHaskell #-}

import Control.Lens
import Data.Monoid

import Control.Monad.Trans.State
import Control.Monad.ListT
import Control.Monad.Trans.Class
import Control.Monad.IO.Class

data Stobjs = Stobjs {
    _x :: Int
  , _y :: String
  }

makeLenses ''Stobjs

main = runListT . (`runStateT`Stobjs 10 "") $ do
   δx <- lift $ return 1 <> return 2 <> return 3
   xnow <- x <+= δx
   y .= show xnow
   if xnow > 11 then liftIO . putStrLn =<< use y
                else lift mempty

(выходы 12).

"Возможность создавать их по желанию" немного сложнее, потому что добавление переменных возможно только через изменение объекта состояния, что означает, что вы больше не будете в той же монаде. Объектив имеет понятие масштабирования, которое можно использовать - разделение объекта состояния на "области видимости" и использование вычислений, в которых только некоторые переменные определены как увеличенные в этой области.

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

В будущем у нас будет OverloadedRecordFields расширение, которое поможет с такими вещами.

Источник

Этот ответ не рекомендуется, смотрите другой.

Чтобы расширить вашу идею обернуть StateT со слабо типизированной картой переменных это будет выглядеть примерно так:

{-# LANGUAGE GADTs #-}

import Unsafe.Coerce
import Data.IntMap

data WeakTyped where
   WeakTyped :: a -> WeakTyped

newtype STT' m a = STT' { weakTypState :: StateT (IntMap WeakTyped) m a }
  deriving (Functor, Applicative, Monad)

newtype STT'Ref a = STT'Ref { mapIndex :: Int }

newSTTRef :: Monad m => a -> STT' m (STT'Ref a)
newSTTRef x = STT' $ do
   i <- (+1) . maximum . keys <$> get
   modify $ insert i x
   return $ STT'Ref i

readSTTRef :: Monad m => STT'Ref a -> STT' m a
readSTTRef (STT'Ref i) = STT' $ do
   unsafeCoerce . (!i) <$> get

Я не уверен, что это будет действительно разумно. Эти STT'Refони не обрабатываются должным образом средой выполнения Haskell, в частности переменные состояния не будут собирать мусор. Таким образом, если вы запускаете действие, которое использует newSTTRef в цикле, это на самом деле будет расти IntMap в каждой итерации, не освобождая переменные, которые уже вышли из области видимости (т.е. не имеют ссылок на них).

Может быть возможно добавить фактический сборщик мусора ко всему этому, но это сделало бы это намного более сложным.

Источник
Другие вопросы по тегам