在Haskell中左侧递归>> =

Question

我刚读过这篇非常有趣的文章,关于Prompt Monad 的另一种实现:http://joeysmandatory.blogspot.com/2012/06/explaining-prompt-monad-with-simpler.html

这是一个可以运行的简化代码:

data Request a where
    GetLine  :: Request String
    PutStrLn :: String -> Request ()

data Prompt p r
     = forall a. Ask (p a) (a -> Prompt p r)
    | Answer r

instance Monad (Prompt p) where
    return              = Answer
    Ask req cont >>= k  = Ask req (\ans -> cont ans >>= k)
    Answer x >>= k      = k x

prompt :: p a -> Prompt p a
prompt req = Ask req Answer

runPromptM :: Monad m => (forall a. p a -> m a) -> Prompt p r -> m r
runPromptM perform (Ask req cont) = perform req
                            >>= runPromptM perform . cont
runPromptM _       (Answer r)     = return r

handleIO :: Request a -> IO a
handleIO GetLine = return ""
handleIO (PutStrLn s) = putStrLn s

req :: Prompt Request ()
req = do
  answers <- sequence $ replicate 20000 (prompt GetLine)
  prompt $ PutStrLn (concat answers)

main = runPromptM handleIO req

文章中的评论提到:

它有一个问题,即递归>> =需要二次时间来评估(它与++问题的左递归相同!)

我不明白二次时间(我通过实验检查)的来源.它与懒惰评估有关吗？

有人能解释一下为什么吗？

Answer 1

我觉得使用Freemonad 更容易解释Prompt,尽管它们非常相似.

data Free f a = Pure a | Free (f (Free f a)) deriving Functor

该Free单子或者是一个已完成由标记操作Pure或f通过标记-indexed效果Free.如果f是,Functor那么Free f是Monad

instance Functor f => Monad (Free f) where
  return = Pure
  Pure a >>= f = f a
  Free m >>= f = Free (fmap (>>= f) m)

这个Monad实例通过"推动"工作,通过层的各个层向下Functor到达Pure底部的节点,然后应用f.对此重要的是Functor层数不会改变.也就是说,这是一个发生的绑定示例Free Maybe ().

Free (Just (Free (Just (Free Nothing)))) >>= (const (return ()))
Free (fmap (>>= (const (return ()))) (Just (Free (Just (Free Nothing))))
Free (Just (Free (Just (Free Nothing)) >>= (const (return ())))
Free (Just (Free (fmap (>>= (const (return ()))) (Just (Free Nothing))))
Free (Just (Free (Just (Free Nothing >>= (const (return ()))))))
Free (Just (Free (Just (Free Nothing))))

我们在这里看到了一些暗示即将到来的东西 - 我们必须遍历整个树到根,只是什么都不做.

"树嫁接"替代蒙纳德

看Free单子的一种方法是将其视为"替代单子".它的绑定看起来像

(=<<) :: (a -> Free f b) -> Free f a -> Free f b

如果您认为a -> Free f b将Pure叶值转换为新的效果树,则(=<<)只需通过效果树下降Free f a并对a值进行替换.

现在,如果我们有一系列正确的关联绑定(使用Kleisli编写(>=>)来证明重新关联是有效的 - Kleisli箭头是一个类别)

f >=> (g >=> h)

那么我们只需要下降到树中一次 - 在树的所有节点上计算替换函数.但是,如果我们与另一个方向联系在一起

(f >=> g) >=> h

我们得到相同的结果,但必须在我们能够应用替换函数之前计算整个结果 .这意味着如果我们有一个深度嵌套的左关联绑定序列(f >=> g)h

((((f >=> g) >=> h) >=> i) >=> j) >=> k

然后我们不断重新计算左边的结果,以便我们可以对它们进行重新计算.这是二次减速出现的地方.

密码加速

有一个非常奇怪的类型叫做Codensity延续传递风格和ContTmonad.

data Codensity m a = Codensity { runCodensity :: forall b . (a -> m b) -> m b }

--   Codensity m a = forall b . ContT b m a

Codensity有一个有趣的特性,Functor即使m不是:

instance Functor (Codensity m) where
  fmap f m = Codensity (\amb -> runCodensity m (amb . f))

以及它的独特属性Monad即使m不是:

instance Monad (Codensity m) where
  return a = Codensity (\amb -> amb a)
  m >>= f = Codensity (\bmc -> runCodensity m (\a -> runCodensity (f a) bmc))

我们还可以往返Monads至Codensity

toCodensity :: Monad m => m a -> Codensity m a
toCodensity ma = Codensity (\amb -> ma >>= amb)

fromCodensity :: Monad m => Codensity m a -> m a
fromCodensity m = runCodensity m return

roundtrip :: Monad m => m a -> m a
roundtrip = fromCodensity . toCodensity

但是当我们这样做时,非常非常有趣的事情发生了:所有的绑定都变得正确了!.

Answer 2

考虑经典的左关联追加问题。您可能知道，每当您有一系列左关联的类似追加的函数（我将(++)在此处使用）时，您都会遇到O(n^2)问题：

(((as ++ bs) ++ cs) ++ ds) ++ ...

很容易看出，每个附加附加都必须遍历先前附加列表的整个长度，导致O(n^2)算法极其缓慢。

解决方案是右关联：

as ++ (bs ++ (cs ++ (ds ++ ...)))

这是O(a + b + c + d + ...)等a的长度as或简单地O(n)在总列表的长度中的位置。

现在，这有什么关系Free？Free让我们建议性地比较和的定义[]：

data Free f r = Pure r | Free (f (Free f r))
data []     a = []     | Cons a [a]

虽然每个节点[]都有值，但只有尖端有值。除此之外，定义非常相似。一个很好的直觉是它是 s 的类似列表的数据结构。ConsFreePureFreeFunctor

现在的Monad实例Free，我们只关心(>>=)：

Pure r >>= f = f r
Free x >>= f = Free (fmap (>>= f) x)

请注意，(>>=)遍历 的结构Free直到达到该Pure值，然后将附加Free结构移植（追加）到末尾。惊人地相似(++)！

Free有了作为 的列表Functor和(>>=)作为 的列表的直觉(++)，应该清楚为什么 left Associated(>>=)会导致问题。