Есть ли разумный способ расстегнуть молнию на государственной монаде?

Question

Мне бы хотелось иметь такую ​​функцию:

unzipState :: (MonadState s m) => m (a, b) -> (m a, m b)

, которая бы выполняла (с сохранением состояния) вычисления, которые возвращали бы кортеж, и возвращала бы два (зависимых) вычисления.

Сложность, конечно, заключается в том, что извлечение значений из одного или другого вычисления должно обновлять состояние в другом.

Полезным (и мотивирующим) приложением является случайная монада, выраженная как

{-# LANGUAGE Rank2types #-}
import qualified System.Random as SR
import Control.Monad.State

type Random a = forall r. (State RandomGen r) => State r a

и скажем, у вас есть:

normal :: Random Double
-- implementation skipped

correlateWith :: Double -> Random (Double, Double) -> Random (Double, Double)
correlateWith rho w = do
                        (u, v) <- w
                        return $ (u, p * u + (1 - p * p) * v)

было бы вполне естественно иметь возможность написать:

let x = normal
    y = normal
    (u, v) = unzipState $ correlateWith 0.5 $ liftM2 (,) x y
    ... now I am able to perform computation on u and v as correlated random variables

Есть ли разумный способ сделать это?Я немного боролся, но не смог добраться ни к чему.Hoogle тоже не помог.

edit

Отличные ответы показали, что моя проблема плохо определена.Тем не менее, кто-то может объяснить мне , почему следующая реализация в python (которую я считаю правильной, но не очень много проверенной) не может быть переведена в Haskell (с магией STrefs, замыканий и других вещей, которые я допускаюЯ не понимаю ;-)):

def unzipState(p):
    flist, glist = [], []
    def f(state):
        if not flist:
            (fvalue, gvalue), newstate = p(state)
            glist.insert(0, gvalue)
            return (fvalue, newstate)
        else:
            fvalue = flist.pop()
            return (fvalue, state)
    def g(state):
        if not glist:
            (fvalue, gvalue), newstate = p(state)
            flist.insert(0, fvalue)
            return (fvalue, newstate)
        else:
            gvalue = glist.pop()
            return (gvalue, state)
    return (f, g)

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

edit2

Теперь это кристально ясно.Функтоны f и g, очевидно, не являются чистыми, поскольку их вывод зависит не только от значения состояния.

Еще раз спасибо!

Answer 1

Это невозможно создать общую функцию unzipState, которая делает то, что вы хотите, хотя бы потому, что вы, вероятно, не можете предоставить формальную спецификацию для ее предполагаемого эффекта.Другими словами, предположим, что вы реализовали некоторую функцию unzipState.Откуда ты знаешь, что это правильно?Вам нужно будет доказать, что он удовлетворяет определенным законам / уравнениям, но проблема здесь в том, чтобы найти эти законы в первую очередь.

Хотя я думаю, что понимаю, что вы хотите сделать, Random Монада также дает понять, почему этого нельзя сделать.Чтобы увидеть это, вы должны отказаться от конкретной реализации type Random a = ... и рассмотреть абстрактную интерпретацию, заданную

v :: Random a означает, что v представляет собой распределение вероятностей значенийтипа a

Операция «связывания» (>>=) :: Random a -> (a -> Random b) -> Random b - это просто способ построить новое распределение вероятностей из старого распределения вероятностей.

Теперь это означает, что unzipState просто возвращает пару распределений вероятностей, которые можно использовать для построения других распределений вероятностей.Дело в том, что хотя синтаксис do выглядит очень многообещающе, но вы на самом деле не выбираете случайных величин, вы просто рассчитываете распределения вероятностей.Случайные переменные могут коррелироваться, но распределение вероятностей не может.

Обратите внимание, что можно создать другую монаду RandomVariable a, которая соответствует случайным переменным.Тем не менее, вы должны исправить пробное пространство Ω заранее.Реализация:

type RandomVariable a = Ω -> a

---

Если вам нужны обе случайные величины и возможность автоматического увеличения выборочного пространства, вам, вероятно, понадобятся две операции связывания

bind1 :: Random Ω a -> (a -> Random Ω b) -> Random Ω b
bind2 :: Random Ω1 a -> (a -> Random Ω2 b) -> Random (Ω1,Ω2) b

и некоторая магия зависимого типа для борьбы с распространением таких продуктов, как (Ω1,(Ω2,Ω3)).

Answer 2

Мне не совсем понятно, как бы вы хотели, чтобы это работало - поскольку correlateWith работает с кортежем, какое значение будут иметь коррелированные переменные независимо?Допустим, вы делаете это:

let x = normal
    y = normal
    (u, v) = unzipState $ correlateWith 0.5 $ liftM2 (,) x y
in do u1 <- u
      v1 <- v
      u2 <- u
      u3 <- u
      -- etc...

Какая связь должна существовать между u1, u2 и u3?

Кроме того, подобную «случайную переменную» можно преобразоватьв бесконечный ленивый поток прямым способом.Что будет означать следующее:

let x = normal
    y = normal
    (u, v) = unzipState $ correlateWith 0.5 $ liftM2 (,) x y
in do vs <- generateStream v
      u1 <- u
      if someCondition u1 then u else return u1
      -- etc...

Поскольку число значений, выбранных из u, изменяется в зависимости от u1, это, по-видимому, указывает на то, что немонадное значение связано с vsзадним числом будет зависеть как-то от u1, что подозрительно похоже на жуткий поступок на расстоянии, которого избегает Хаскелл.

Я бы рискнул догадаться, что то, чего вы пытаетесь достичь, просто не можетбыть модифицированным поверх простой монады состояния PRNG, но возможны и другие варианты.

Answer 3

На байесовских монадах в Хаскеле много чего похожего. Вот одна ссылка: http://www.randomhacks.net/articles/2007/02/22/bayes-rule-and-drug-tests

См. Также «Чисто функциональное ленивое недетерминированное программирование», доступное на этой странице: http://www.cs.rutgers.edu/~ccshan/

Редактировать: я также не понимаю, почему вы не можете просто дать correlateWith следующую сигнатуру типа и запустить ее внутри блока do напрямую, а не пытаться "вставить" случайное состояние в привязку let. correlateWith :: Double -> Random Double -> Random Double -> Random (Double, Double)