阐明 Continuation Monad 实例的实现

Question

下面是我为 Continuation Monad 尝试的代码示例

newtype Cont r a = Cont { rC :: (a -> r) -> r }

instance Functor (Cont r) where
  fmap :: (a -> b) -> Cont r a -> Cont r b
  fmap f (Cont aCont) = Cont $ \k -> aCont (\a -> k (f a))

instance Applicative (Cont r) where
  pure :: a -> Cont r a
  pure a = Cont $ \k -> k a

  (<*>) :: Cont r (a -> b) -> Cont r a -> Cont r b
  Cont fCont <*> Cont aCont = Cont $ \k -> fCont (\f -> aCont (\a -> k (f a)))

instance Monad (Cont r) where
  return = pure

  (>>=) :: Cont r a -> (a -> Cont r b) -> Cont r b
  Cont aCont >>= f = Cont $ \k -> rC (aCont (\a -> f a)) (\b -> k b)
  -- f a :: Cont r b
  -- aCont :: (a -> r) -> r
  -- t = aCont (\a -> f a) :: Cont r b
  -- t' = rc t :: (b -> r) -> r
  -- k :: b -> r
  -- t' (\b -> k b) -> r

这是失败与以下错误

<interactive>:158:52: error:
    * Occurs check: cannot construct the infinite type: r ~ Cont r b
    * In the expression: f a
      In the first argument of `aCont', namely `(\ a -> f a)'
      In the first argument of `rC', namely `(aCont (\ a -> f a))'
    * Relevant bindings include
        k :: b -> r (bound at <interactive>:158:30)
        f :: a -> Cont r b (bound at <interactive>:158:18)
        aCont :: (a -> r) -> r (bound at <interactive>:158:8)
        (>>=) :: Cont r a -> (a -> Cont r b) -> Cont r b
          (bound at <interactive>:158:14)

当我更改如下绑定代码时，它起作用了。请帮我解决类型错误。

  (>>=) :: Cont r a -> (a -> Cont r b) -> Cont r b
  Cont aCont >>= f = Cont $ \k -> aCont (\a -> rC (f a) (\b -> k b))

Answer 1

在我看来，您只是感到困惑-我发现使用延续很容易！

这个定义：

newtype Cont r a = Cont { rC :: (a -> r) -> r }

“免费”定义了 2 个函数：

Cont :: ((a -> r) -> r) -> Cont r a
rC :: Cont r a -> (a -> r) -> r

然后在您对 的尝试定义中>>=，您有：

Cont aCont >>= f = Cont $ \k -> rC (aCont (\a -> f a)) (\b -> k b)

HereaCont (\a -> f a)用作 的参数rC，因此必须具有 type Cont r a。同时，由于Cont是具有上述类型的构造函数，因此Cont aContGHC 必须分配给aCont类型(a -> r) -> r。这反过来意味着f a必须有 type r，而a有 type a -> r。

但从类型来说>>=，f必须有类型a -> Cont r b。所以f a必须同时是rand类型Cont r b，并且试图使这两种类型相同显然涉及无限回归 - 这正是 GHC 告诉你的。

然而，上面的细节并不是很重要。显而易见的是，aCont它已经“解包”了，您不需要对其应用解包函数rC。