Добавление генерации случайных чисел в монаду STM в Haskell

Question

В настоящее время я работаю над некоторыми тестами транзакционной памяти в Haskell и хотел бы иметь возможность использовать случайные числа в транзакции. Я в настоящее время использую Random монаду / монадный преобразователь отсюда. В следующем примере у меня есть массив TVars, содержащий целые числа и транзакцию, которая случайным образом выбирает 10 твар в массиве для увеличения, например:

tvars :: STM (TArray Int Int)
tvars = newArray (0, numTVars) 0

write :: Int -> RandT StdGen STM [Int]
write 0 = return []
write i = do
    tvars <- lift tvars
    rn <- getRandomR (0, numTVars)
    temp <- lift $ readArray tvars rn
    lift $ writeArray tvars rn (temp + 1)
    rands <- write (i-1)
    lift $ return $ rn : rands

Я думаю, мой вопрос: "Это лучший способ сделать это?" Кажется, что было бы более естественно / эффективно пойти другим путем, то есть поднять случайную монаду в монаду STM. Каждая транзакция выполняет много операций STM и очень мало случайных операций. Я бы предположил, что каждый lift добавляет некоторое количество накладных расходов. Разве это не будет более эффективным, только lift случайные вычисления и оставить вычисления STM в покое? Это даже безопасно сделать? Кажется, что определение преобразователя монады STM нарушило бы хорошие свойства статического разделения, которые мы получаем с монадой STM (то есть мы могли бы поднять IO в монаду STM, но тогда нам нужно беспокоиться об отмене действий IO, если транзакция прерывается, что представляет количество вопросов). Мои знания о монадных трансформаторах довольно ограничены. Краткое объяснение относительно производительности и относительных накладных расходов на использование трансформатора будет высоко ценится.

Answer 1

STM - это базовая монада. atomically, который в настоящее время STM a -> IO a должно выглядеть, если бы мы имели STMT,

У меня есть несколько решений вашей конкретной проблемы. Проще всего, вероятно, перестроить код:

write :: Int -> RandT StdGen STM [Int]
write n = do
   -- random list of indexes, so you don't need to interleave random and stm code at all
   rn <- getRandomRs (0, numTVars) 
   lift $ go rn
   where go []     = return []
         go (i:is) = do tvars <- tvars -- this is redundant, could be taken out of the loop
                        temp <-  readArray tvars i
                        writeArray tvars i (temp + 1)
                        rands <- go is
                        return $ i : rands

---

Все же RandT по существу StateT с lift:

instance MonadTrans (StateT s) where
    lift m = StateT $ \ s -> do
        a <- m
        return (a, s)

Итак, код формы:

do x <- lift baseAction1
   y <- lift baseAction2
   return $ f x y

Будет

do x <- StateT $ \s -> do { a <- baseAction1; return (a, s) }
   y <- StateT $ \s -> do { a <- baseAction2; return (a, s) }
   return $ f x y

который после desugaring сделать запись

StateT (\s -> do { a <- baseAction1; return (a, s) }) >>= \ x ->
StateT (\s -> do { a <- baseAction2; return (a, s) }) >>= \ y ->
return $ f x y

вначале >>=

StateT $ \s -> do
  ~(a, s') <- runStateT (StateT (\s -> do { a <- baseAction1; return (a, s) })) s
  runStateT ((\ x -> StateT (\s -> do { a <- baseAction2; return (a, s) }) >>= \ y -> return $ f x y) a) s'

StateT а также runStateT отменяет:

StateT $ \s -> do
  ~(x, s') <- do { a <- baseAction1; return (a, s) }))
  runStateT ((\ x -> StateT (\s -> do { a <- baseAction2; return (a, s) }) >>= \ y -> return $ f x y) x) s'

И после нескольких шагов встраивания / сокращения:

StateT $ \s -> do
  ~(x, s') <- do { a <- baseAction1; return (a, s) }))
  ~(y, s'') <- do { a <- baseAction2; return (a, s') }))
  return (f x y, s'')

Возможно, GHC достаточно умен, чтобы уменьшить это еще дальше, поэтому состояние просто передается без создания промежуточных пар (но я не уверен, что для оправдания этого следует использовать законы монады):

StateT $ \s -> do
   x <- baseAction1
   y <- baseAction2
   return (f x y, s)

что вы получаете от

lift do x <- baseAction1
        y <- baseAction2
        return $ f x y