如何使用递归方案在Haskell中表达此概率分布

Question

这个问题是部分理论/部分实施.背景假设:我使用monad-bayes库将概率分布表示为monad.分布p(a | b)可以表示为函数MonadDist m => b -> m a.

假设我有一个条件概率分布s :: MonadDist m => [Char] -> m Char.我想获得一个新的概率分布sUnrolled :: [Char] -> m [Char],在数学上(我认为)定义为:

sUnrolled(chars|st) = 
              | len(chars)==1 -> s st
              | otherwise -> s(chars[-1]|st++chars[:-1]) * sUnrolled(chars[:-1]|st)

直觉是你采取得到分布st :: [Char],采样新的焦炭c从s st,喂养st++[c]回s,等等.我相信iterateM s或多或少是我想要的.为了使它成为我们实际可以看到的分布,让我们说如果我们击中某个角色,我们就会停下来.然后iterateMaybeM工作.

理论问题:由于各种原因,如果我能用更一般的术语来表达这种分布是非常有用的,例如,在给定随机余代数的情况下推广到树的随机构造的方式.看起来我在这里有某种变形(我意识到数学定义看起来像一个变形,但在代码中我想建立字符串,而不是将它们解构为概率)但我不能完全弄清楚细节,而不是至少是因为存在概率monad.

实际问题:例如,在Haskell中以使用递归方案库的方式实现它也是有用的.

Answer 1

我不够聪明，无法通过递归方案对单子进行线程化，因此我依赖于 recursion-schemes-ext，它具有 anaM 函数，用于运行附加单子操作的变形。

我在这里做了一个（非常丑陋的）概念证明：

{-# LANGUAGE FlexibleContexts #-}
import Data.Functor.Foldable (ListF(..), Base, Corecursive)
import Data.Functor.Foldable.Exotic (anaM)
import System.Random

s :: String -> IO (Maybe Char)
s st = do
  continue <- getStdRandom $ randomR (0, 2000 :: Int)
  if continue /= 0
    then do
    getStdRandom (randomR (0, length st - 1)) >>= return . Just . (st !!)
    else return Nothing


result :: (Corecursive t, Traversable (Base t), Monad m) => (String -> m (Base t String)) -> String -> m t
result f = anaM f

example :: String -> IO (Base String String)
example st = maybe Nil (\c -> Cons c $ c:st) <$> s st

final :: IO String
final = result example "asdf"

main = final >>= print

一些注释

1. 我模拟了你的s功能，因为我不熟悉monad-bayes
2. 由于我们的最终列表位于 monad 内，因此我们必须严格构建它。这迫使我们制作一个有限的列表（我允许我的s函数随机停止在 2000 个字符左右）。

编辑：

下面是一个修改版本，确认结果函数可以生成其他递归结构（在本例中为二叉树）。请注意， 的类型final和 的值example是先前代码中唯一发生更改的两位。

{-# LANGUAGE FlexibleContexts, TypeFamilies #-}
import Data.Functor.Foldable (ListF(..), Base, Corecursive(..))
import Data.Functor.Foldable.Exotic (anaM)
import Data.Monoid
import System.Random

data Tree a = Branch a (Tree a) (Tree a) | Leaf
  deriving (Show, Eq)
data TreeF a b = BranchF a b b | LeafF

type instance Base (Tree a) = TreeF a
instance Functor Tree where
  fmap f (Branch a left right) = Branch (f a) (f <$> left) (f <$> right)
  fmap f Leaf = Leaf
instance Functor (TreeF a) where
  fmap f (BranchF a left right) = BranchF a (f left) (f right)
  fmap f LeafF = LeafF
instance Corecursive (Tree a) where
  embed LeafF = Leaf
  embed (BranchF a left right) = Branch a left right
instance Foldable (TreeF a) where
  foldMap f LeafF = mempty
  foldMap f (BranchF a left right) = (f left) <> (f right)
instance Traversable (TreeF a) where
  traverse f LeafF = pure LeafF
  traverse f (BranchF a left right) = BranchF a <$> f left <*> f right

s :: String -> IO (Maybe Char)
s st = do
  continue <- getStdRandom $ randomR (0, 1 :: Int)
  if continue /= 0
    then getStdRandom (randomR (0, length st - 1)) >>= return . Just . (st !!)
    else return Nothing


result :: (Corecursive t, Traversable (Base t), Monad m) => (String -> m (Base t String)) -> String -> m t
result f = anaM f

example :: String -> IO (Base (Tree Char) String)
example st = maybe LeafF (\c -> BranchF c (c:st) (c:st)) <$> s st

final :: IO (Tree Char)
final = result example "asdf"

main = final >>= print