建立在Haskell

Question

具有不确定性的单子变压器我想建在Haskell一个不确定的单子转换，我认为，从ListT和ListT建议在http://www.haskell.org/haskellwiki/ListT_done_right替代不同的行为。其中第一个将monad与一系列项目联系起来;第二种将单子与单个项目联系起来，但具有以下特性：给定元素中的单子动作影响列表中后续插槽中的单子元素。我们的目标是建立形式

data Amb m a = Cons (m a) (Amb m a) | Empty 

的单子转换，使该列表的每一个元素都有与它相关联自己的单子，并且连续元素具有独立的单子。在这篇文章的最后，我对这个monad应该给出的这种行为有一些证明。如果你知道如何获得ListT的一些变体来提供这种行为，那也是有帮助的。

以下是我的尝试。它不完整，因为unpack函数未定义。我怎样才能定义它？下面是在它定义一个不完整的企图，但是当单子M含有的Empty大使名单不采取了这样的情况：

unpack :: (Monad m) => m (Amb m a) -> Amb m a                             
unpack m = let first = join $ do (Cons x ys) <- m                            
           return x                              
       rest = do (Cons x ys) <- m                              
          return ys                               
      in Cons first (unpack rest) 

满（不完全）代码：

import Prelude hiding (map, concat)                               
import Control.Monad                                   
import Control.Monad.Trans  

data Amb m a = Cons (m a) (Amb m a) | Empty                             

infixr 4 <:>                                     
(<:>) = Cons                                     

map :: Monad m => (a -> b) -> Amb m a -> Amb m b                            
map f (Cons m xs) = Cons y (map f xs)                               
    where y = do a <- m                                  
       return $ f a                                 
map f Empty = Empty                                   

unpack :: m (Amb m a) -> Amb m a                                
unpack m = undefined                                   


concat :: (Monad m) => Amb m (Amb m a) -> Amb m a                            
concat (Cons m xs) = (unpack m) `mplus` (concat xs)                           
concat Empty = Empty                                   

instance Monad m => Monad (Amb m) where                              
    return x = Cons (return x) Empty                               
    xs >>= f = let yss = map f xs                                
       in concat yss                                 

instance Monad m => MonadPlus (Amb m) where                             
    mzero = Empty                                    
    (Cons m xs) `mplus` ys = Cons m (xs `mplus` ys)                           
    Empty `mplus` ys = ys                                  

instance MonadTrans Amb where                                 
    lift m = Cons m Empty   

期望的行为的实例

这里，基单子是State Int

instance Show a => Show (Amb (State Int) a) where                            
    show m = (show . toList) m                                


toList :: Amb (State Int) a -> [a]                                
toList Empty = []                                    
toList (n `Cons` xs) = (runState n 0 : toList xs)                            


x = (list $ incr) >> (incr <:> incr <:> Empty)                             
y = (list $ incr) >> (incr <:> (incr >> incr) <:> Empty)                          

main = do                                      
    putStr $ show x -- | should be [2, 2]                              
    putStr $ show y -- | should be [2, 3] 

谢谢。

更新：为什么LogicT没有做我想做的例子。

这里就是LogicT做上面的简单的例子：

import Control.Monad                                   
import Control.Monad.Logic                                  
import Control.Monad.State                                  

type LogicState = LogicT (State Int)                               


incr :: State Int Int                                   
incr = do i <- get                                    
      put (i + 1)                                   
      i' <- get                                   
      return i'                                   

incr' = lift incr                                    
y = incr' >> (incr' `mplus` incr')                               

main = do                                      
    putStrLn $ show (fst $ runState (observeAllT y) 0) -- | returns [2,3], not [2,2]                          

Answer 1

我相信你可以使用StateT。例如：

import Control.Monad.State 

incr = modify (+1) 
sample1 = incr `mplus` incr 
sample2 = incr `mplus` (incr >> incr) 

monomorphicExecStateT :: StateT Int [] a -> Int -> [Int] 
monomorphicExecStateT = execStateT 

main = do 
    print (monomorphicExecStateT sample1 0) -- [1, 1] 
    print (monomorphicExecStateT sample2 0) -- [1, 2] 

Answer 2

我不认为这是可能在一般情况下（和单子转换应该是能够改变任何单子）。你提到的解压缩选项是不可能的，一般单子 - 它所对应的操作：

extract :: (Comonad w) => w a -> a 

这是一个comonad（数学双单子的）的操作。

有些事情可以通过采取（m（Amb ma））并将其映射几次以产生单个（ma）来解压缩它，但这需要您事先知道（或者更确切地说，来自monad外部）正在创建多少个选择，如果没有某种形式的提取操作，这些选择是不可能知道的。

在第二个ListT中列表的尾部取决于一次性动作的原因是因为我们需要在某些情况下执行一次性动作，以便找出正在生成多少个选项（以及多长时间列表是）。