问使用连续monad在“the”(和其他有约束的容器)上构造有效的monad实例

EN

Monad是一种特殊的构造和排序计算方法。一个单一的绑定不能神奇地重组你的计算，以便以一种更有效的方式发生。计算的结构有两个问题。

1. 在评价stepN 20 0时，step 0的计算结果将进行20次计算。这是因为计算的每一步都生成0作为一个备选方案，然后将其输入到下一个步骤，该步骤也生成0作为替代，等等…… 或许这里的回忆录能帮上忙。
2. 一个更大的问题是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 0 setBind (\x1 -> step x1 setBind (\x2 -> step x2 setBind (\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的集合的元素。

最近在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 -}

在这种情况下，我不认为您的性能问题是由于使用了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 . toSet