使用连续monad在“the”(和其他有约束的容器)上构造有效的monad实例
Set，类似于[]，有一个完全定义的一元操作。问题是，它们要求值满足Ord约束，因此不可能在没有任何约束的情况下定义return和>>=。同样的问题也适用于需要对可能值进行某种约束的许多其他数据结构。
标准的技巧(在haskell-咖啡馆邮报中建议我这样做)是将Set封装到连续单元中。ContT不在乎底层类型函子是否有任何约束。只有在将Set包装/解包装为连续/从连续性时，才需要约束：
import Control.Monad.Cont
import Data.Foldable (foldrM)
import Data.Set
setReturn :: a -> Set a
setReturn = singleton
setBind :: (Ord b) => Set a -> (a -> Set b) -> Set b
setBind set f = foldl' (\s -> union s . f) empty set
type SetM r a = ContT r Set a
fromSet :: (Ord r) => Set a -> SetM r a
fromSet = ContT . setBind
toSet :: SetM r r -> Set r
toSet c = runContT c setReturn这可以根据需要工作。例如，我们可以模拟一个非确定性函数，它要么将其参数增加1，要么保持不变：
step :: (Ord r) => Int -> SetM r Int
step i = fromSet $ fromList [i, i + 1]
-- repeated application of step:
stepN :: Int -> Int -> Set Int
stepN times start = toSet $ foldrM ($) start (replicate times step)实际上，stepN 5 0产生了fromList [0,1,2,3,4,5]。如果我们使用[] monad代替，我们将得到
[0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5]而不是。
问题是效率。如果我们调用stepN 20 0，输出需要几秒钟，而stepN 30 0没有在合理的时间内完成。结果表明，所有Set.union操作都是在最后执行的，而不是在每次一元计算之后执行。其结果是成倍地构造了许多Set，并且只在最后编写了union，这对于大多数任务来说都是不可接受的。
有什么办法可以绕过它，使这个建筑高效吗？我试过了，但没有成功。
(我甚至怀疑库里-霍华德同构和Glivenko定理可能有一些理论上的限制。Glivenko定理指出，对于任何命题重言式φ，φ公式都可以在直觉逻辑中得到证明。然而，我怀疑证明的长度(以正常形式)可以是指数长的。那么，也许在某些情况下，将计算封装到连续单元中会使其成倍增长？)
回答 4
Stack Overflow用户
发布于 2012-08-30 06:50:17
Monad是一种特殊的构造和排序计算方法。一个单一的绑定不能神奇地重组你的计算，以便以一种更有效的方式发生。计算的结构有两个问题。
- 在评价
stepN 20 0时，step 0的计算结果将进行20次计算。这是因为计算的每一步都生成0作为一个备选方案，然后将其输入到下一个步骤，该步骤也生成0作为替代，等等…… 或许这里的回忆录能帮上忙。 - 一个更大的问题是
ContT对计算结构的影响。通过一些等式推理，扩展了replicate 20 step的结果，定义了foldrM并根据需要进行了多次简化，我们可以看到stepN 20 0相当于： (.(返回0 >>=步骤) >>= .) 此表达式的所有括号都与左侧关联。这很好，因为这意味着每个(>>=)的RHS都是一个基本的计算，即step，而不是一个组合的计算。然而，放大了(>>=)用于ContT的定义， M >>= k= ContT $ \c -> runContT m(a -> runContT (k ) c) 我们看到，当计算一个与左关联的(>>=)链时，每个绑定都会将一个新的计算推到当前的延续c上。为了说明正在发生的事情，我们可以再次使用一些等式推理，扩展(>>=)的定义和runContT的定义，并简化，生成： setReturn 0setBind(\x1 -> step x1setBind(\x2 -> step x2setBind(\x3 -> .)) 现在，对于每个发生的setBind，让我们问自己RHS的论点是什么。对于最左边的情况，RHS参数是setReturn 0之后的整个计算过程。对于第二次出现，这是step x1之后的所有内容，等等。让我们放大到setBind的定义： setBind集f= foldl‘(\s ->并s.( f)空集 在这里，f表示计算的所有其余部分，setBind出现的右侧的所有内容。这意味着，在每一步中，我们都以f的形式捕获计算的其余部分，并尽可能多地应用f，就像set中的元素一样。计算不像以前那样是基本的，而是合成的，这些计算将被重复多次。
问题的症结在于，ContT单体转换器正在将计算的初始结构(您指的是setBind's的左结合链)转换为一个具有不同结构(即右结合链)的计算。这毕竟是非常好的，因为其中一条单数定律说，对于每一个m、f和g，我们都有这样的计算。
(m >>= f) >>= g = m >>= (\x -> f x >>= g)然而，单一法则并没有将复杂性强加于每一个定律方程的每一个侧面。实际上，在这种情况下，构造这个计算的左结合方式是更有效的。setBind's的左关联链不需要时间计算，因为只有初等子计算是重复的。
事实证明，其他解决方案--将Set压缩为单一产品--也面临着同样的问题。特别是，集单包产生类似的运行时。其原因是，它也将左关联表达式重写为右关联表达式。
我认为您已经把手指放在了一个上，这是非常重要的，但也是相当微妙的问题，坚持Set必须遵守Monad接口。我认为这是无法解决的。问题是单播的绑定类型需要是
(>>=) :: m a -> (a -> m b) -> m b在a或b上都不允许类约束。这意味着我们不能在左边嵌套绑定，除非首先调用monad规则来重写为右关联链。原因如下:给定(m >>= f) >>= g，计算(m >>= f)的类型为m b形式。计算(m >>= f)的值为b类型。但是，由于不能将任何类约束挂在类型变量b上，所以我们无法知道得到的值是否满足Ord约束，因此不能将该值用作我们希望能够计算union的集合的元素。
Stack Overflow用户
发布于 2013-05-13 04:36:01
最近在Haskell 奥列格举了一个例子上，如何有效地实现Set单片。引用：
..。然而，有效的真正的集单是可能的。 ..。随函附寄的是有效的正品单套。我是用直接的方式写的(不管怎样，它看起来更快)。关键是尽可能使用优化的选择函数。 {-#语言GADT、TypeSynonymInstances、FlexibleInstances #-}模块SetMonadOpt，其中导入限定的Data.Set作为S导入Control.Monad数据SetMonad a，其中SMOrd :：Ord a => S.Set a -> SetMonad a SMAny :A -> SetMonad a instance Monad SetMonad其中返回x= SMAny x m >>= f= collect。地图f$ toList m toList :：SetMonad a -> a toList (SMOrd x) = S.toList x toList (SMAny x) =x collect :：SetMonad a -> SetMonad a collect [] = SMAny [] collect x=x collect ((SMOrd x):t) = case collect t of SMOrd y -> SMOrd ( SMOrd X y) SMOrd y en21 20#(X (S.fromList y)) collect ((SMAny x):t) = SMOrd y -> SMOrd (S.union y (S.fromList x)) SMAny y -> SMAny (x ++ y) runSet : Ord a => SetMonad a S.Set a runSet (SMOrd x) =x runSet ( x) =x实例en22#其中mzero = SMAny [] mplus (SMAny x) (SMAny y) = SMAny (x ++ y) mplus (SMAny x) (SMOrd y) = SMOrd (S.union y (S.fromList x)) mplus (SMOrd x) (SMAny y) = SMOrd (S.union x (S.fromList y)) mplus (SMOrd x) (SMOrd y) = SMOrd (S.fromList x y)选择:m a m选择= msum。映射返回test1 = runSet (do n1 <-选择1.5 n2 <-选择1.5让n= n1 + n2保护$n<7返回n) -- fromList 2,3,4,5,6 -可从中选择的值可能是高阶的或动作test1‘= runSet (do n1 <- runSet)。映射返回$ 1..5 n2 <- return。映射返回$1.5 n <- liftM2 (+) n1 n2保卫$n<7返回n) -- fromList 2,3,4,5,6 test2 = runSet (我<-选择1.10j <-选择1.10k <-选择1.10警卫$ i*i + j*j == k*k返回(i，j，k)) - fromList (3,4,5)，(4,3,5)，(6,8,10)，(8,6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，6，610) test3 = runSet (我是否<-选择1.10j <-选择1.10k <-选择1.10警卫$ i*i + j*j == k*k返回k) - fromList 5,10 - Petr Pudlak的测试-首先，一般的，非最优的情况步骤:：(MonadPlus m) => Int -> Int步骤i=选择i，I+1-在0: stepN :：Int -> S.Set Int stepN = runSet上重复应用step。F其中，f0=返回0fn=f (n-1) >>=步骤--它工作，但显然是指数的{- *SetMonad> stepN 14 fromList 0，1，2，3，4，5，6，7，8，9，10，11，12，13 14 *SetMonad> stepN 15 fromList 0、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15 *SetMonad> stepN 16 fromList 0，1，2，3，4，5，6，7，8，9，10，11，12，13 14，15，16 -} --而现在优化的chooseOrd :：Ord a => a -> a chooseOrd x= SetMonad ( x) :：Int en22# Int #23#i= i，I+1-在0: stepNOpt :：Int -> S.Set Int stepNOpt = runSet上重复应用step。F其中f0=返回0fn=f (n-1) >>= stepOpt {- stepNOpt 14 fromList 0，1，2，3，4，5，6，7，8，9，10，11，12，13 14 stepNOpt 15 fromList 0、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15 stepNOpt 16 fromList 0，1，2，3，4，5，6，7，8，9，10，11，12，13 14，15，16 stepNOpt 30 fromList 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30 -}
Stack Overflow用户
发布于 2012-08-29 15:29:14
在这种情况下，我不认为您的性能问题是由于使用了Cont
step' :: Int -> Set Int
step' i = fromList [i,i + 1]
foldrM' f z0 xs = Prelude.foldl f' setReturn xs z0
where f' k x z = f x z `setBind` k
stepN' :: Int -> Int -> Set Int
stepN' times start = foldrM' ($) start (replicate times step')获得与基于Cont的实现类似的性能，但完全发生在Set的“受限单”中。
我不确定我是否相信你关于Glivenko定理的说法导致了(规范化)证明大小的指数增长--至少在逐需要的上下文中是这样。这是因为我们可以任意重用子证明(我们的逻辑是二阶的，我们只需要一个forall a. ~~(a \/ ~a)的证明)。证明不是树，而是图(共享)。
通常，您可能会看到Cont包装Set带来的性能成本，但通常可以通过
smash :: (Ord r, Ord k) => SetM r r -> SetM k r
smash = fromSet . toSethttps://stackoverflow.com/questions/12183656
复制
腾讯云开发者
