haskell - 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

文章中的评论提到:

it has a problem that left recursion of >>= takes quadratic time to evaluate (it's the same as the left-recursion of ++ problem!)

我不明白二次时间(我通过实验检查过)从何而来。与惰性求值有关吗？

有人可以解释一下为什么吗？

Answer 1

我觉得使用 Free 更容易解释一点单子(monad)超过 Prompt ，尽管它们非常相似。

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

Free monad 是一个标记为 Pure 的已完成操作或f -索引效果由 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的各层向下绑定(bind)。到达Pure底部的节点，然后应用 f 。重要的是 Functor 的数量图层不会改变。也就是说，这是一个发生在Free Maybe ()中的示例绑定(bind)。 .

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))))

我们在这里看到了即将发生的事情的暗示——我们必须遍历整棵树直到根部才什么都不做。

“树嫁接”替代单子(monad)

查看 Free 的一种方法monad 是将其视为“替代 monad”。它的绑定(bind)看起来像

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

如果你想到 a -> Free f b作为转换Pure然后将叶子值放入新的效果树 (=<<)只是通过效果树下降 Free f a并对a执行替换值。

现在，如果我们有一个右关联绑定(bind)链(使用 Kleisli 组合 (>=>) 编写，以证明重新关联是有效的 - Kleisli 箭头是一个类别)

f >=> (g >=> h)

那么我们只需下降到树中一次——替换函数在树的所有节点上计算。但是，如果我们关联到另一个方向

(f >=> g) >=> h

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

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

然后我们不断地重新计算左边的结果，以便我们可以递归它们。这就是二次减速出现的地方。

随着密度的加速

有一种非常奇怪的类型叫做 Codensity这与连续传递风格和 ContT 有关单子(monad)。

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

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

Co密度有一个有趣的属性，它是 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))

我们还可以往返Monad已通过 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

但是当我们这样做时something very, very interesting happens: all of the binds become right-associated! .