Haskell版本的阴阳谜题: Kind incompatibility error

Question

我想实现yin-yang puzzle在 haskell 。这是我的尝试(不成功):

-- The data type in use is recursive, so we must have a newtype defined
newtype Cl m = Cl { goOn :: MonadCont m => Cl m -> m (Cl m) }

yinyang :: (MonadIO m, MonadCont m) => m (Cl m)
yinyang = do
    yin <-  (callCC $ \k -> return (Cl k)) >>= (\c -> liftIO (putStr "@") >> goOn c)
    yang <- (callCC $ \k -> return (Cl k)) >>= (\c -> liftIO (putStr "*") >> goOn c)
    goOn yin yang

当查看类型时，显然 callCC $\k -> return (Cl k) 给出了 m (Cl m)，所以 yin code> 的类型为 Cl m。 yang 是一样的。所以我期望 goOn yin yang 给出最终类型 m (Cl m)。

这个实现看起来不错，但问题是它无法编译!这是我得到的错误:

Couldn't match kind `*' against `* -> *'
Kind incompatibility when matching types:
  m0 :: * -> *
  Cl :: (* -> *) -> *
In the first argument of `goOn', namely `yin'
In a stmt of a 'do' block: goOn yin yang

有办法解决这个问题吗？

更新

虽然我自己找到了答案，但我仍然不明白该错误消息的含义。谁能给我解释一下吗？我已经知道的是，在有问题的版本中， goOn c 返回类似 Cl m -> m (Cl m) 的内容，而不是预期的 m (Cl m )。但这不是您从错误消息中可以获得的信息。

Answer 1

代码中有一个愚蠢的错误。这是正确的实现

newtype CFix m = CFix { goOn :: CFix m -> m (CFix m) }

yinyang :: (MonadIO m, MonadCont m) => m (CFix m)
yinyang = do
    yin <-  (\c -> liftIO (putStr "@") >> return c) =<< (callCC $ \k -> return (CFix k)) 
    yang <- (\c -> liftIO (putStr "*") >> return c) =<< (callCC $ \k -> return (CFix k)) 
    goOn yin yang

运行它非常容易。

main :: IO ()
main = runContT yinyang $ void.return

甚至

main :: IO ()
main = runContT yinyang undefined

虽然后者看起来很吓人，但它是安全的，因为延续永远不会有机会被评估。 (整个表达式将被计算为值 _|_ 因为它永远不会停止)

输出预期结果

@*@**@***...

解释

最初的尝试是直接翻译Scheme版本

(let* (
 (yin
    ((lambda (cc) (display #\@) cc) (call-with-current-continuation (lambda (c) c))))
 (yang
    ((lambda (cc) (display #\*) cc) (call-with-current-continuation (lambda (c) c)))))
(yin yang))

进入 haskell 。对于类型化语言来说，进行上述类型检查的关键是有一个类型 t同构于 t -> t 。在 Haskell 中，这是通过使用 newtype 来完成的关键词。另外，为了产生副作用，我们需要 IO ，但不支持callCC 。为了支持后者，我们需要 MonadCont 。因此，要同时使用两者，我们需要 MonadIO和MonadCont 。另外，newtype必须知道哪个Monad它正在工作，因此它应带有 Monad作为其类型参数。所以现在我们写

newtype CFix m = ...

yinyang :: (MonadIO m, MonadCont m) => m (CFix m)

由于我们正在研究 Monad使用方便do符号。所以let*作业应翻译为 yin <-和yang <- 。在 MonadIO至display我们使用liftIO.putStr 。 call-with-current-continuation翻译为callCC但显然我们不能翻译成id或类似的。让我们暂时搁置这个问题。

我的错误是天真地翻译了显示 block 和callCC的组合运算符。阻止至>>= 。在Scheme或其他严格语言中，参数要在表达式之前计算，因此callCC block 应在显示 block 之前执行。因此，我们将使用=<<而不是>>= 。代码现在看起来

newtype CFix m = ...

yinyang :: (MonadIO m, MonadCont m) => m (CFix m)
yinyang = do
    yin <- (\c -> liftIO (putStr "@") >> return c) =<< (callCC $ ...)
    yang <- (\c -> liftIO (putStr "*") >> return c) =<< (callCC $ ...)
    ...

现在是时候进行类型检查，看看我们应该在 ... 中放入什么内容s。 callCC s 签名是

MonadCont m => ((a -> m b) -> m a) -> m a

所以它的参数有类型

MonadCont m => (a -> m b) -> m a

对于某些类型a和b 。通过查看到目前为止编写的代码，我们很容易得出结论:yin和yang应具有相同类型 callCC返回值m a 。但是，原始架构版本使用 yin和yang作为函数，因此它们的类型为 p -> r 。所以这就是我们需要递归类型和newtype的地方.

获取 m a直接的方法是使用 return ，我们需要类型为 a 的东西。假设这是来 self 们要定义的类型构造函数。现在为 callCC 提供参数我们需要构建一个a来自(a -> m b) 。这就是构造函数的样子。但什么是 b ？一个简单的选择是使用相同的 a 。所以我们有 CFix 的定义:

newtype CFix m = CFix { goOn :: CFix m -> m (CFix m) }

以及 callCC 的实现的参数

\k -> return (CFix k)

我们使用CFix构造 CFix 的构造函数从给定的参数，并使用 return将其包装为所需的类型。

现在，我们如何使用yin (类型 m (CFix m) )作为函数？类型析构函数goOn允许我们提取内部函数，因此我们有最后一个 ... 的定义.

newtype CFix m = CFix { goOn :: CFix m -> m (CFix m) }

yinyang :: (MonadIO m, MonadCont m) => m (CFix m)
yinyang = do
    yin <-  (\c -> liftIO (putStr "@") >> return c) =<< (callCC $ \k -> return (CFix k)) 
    yang <- (\c -> liftIO (putStr "*") >> return c) =<< (callCC $ \k -> return (CFix k)) 
    goOn yin yang

这是该程序的最终版本。