6

这个问题是部分理论/部分实施。背景假设：我使用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]中采样新字符、反馈到中等获得的分布。我相信或多或少是我想要的。为了使它成为我们可以实际查看的分布，假设如果我们击中某个角色，我们就会停止。然后工作。cs stst++[c]siterateM siterateMaybeM

理论问题：由于各种原因，如果我可以用更一般的术语来表达这种分布，那将非常有用，例如，在给定随机余代数的情况下，可以推广到树的随机构造。看起来我在这里有某种变形（我意识到数学定义看起来像变形，但在代码中我想建立字符串，而不是将它们解构为概率）但我不太清楚细节，不是至少是因为概率单子的存在。

实际问题：例如，以使用递归方案库的方式在 Haskell 中实现这一点也很有用。

4

1 回答 1

4

我不够聪明，无法通过递归方案将 monad 线程化，所以我依赖于 recursion-schemes-ext，它具有 anaM 函数，用于运行带有 monadic 动作的变形。

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

{-# 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 个字符处）。

编辑：

下面是一个修改版本，确认结果函数可以生成其他递归结构（在本例中为二叉树）。注意 type offinal和 value ofexample是前面代码中仅有的两个发生变化的位。

{-# 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
于 2018-04-17T11:52:44.927 回答