10

我想在 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)给出了 a m (Cl m)，所以yin是 type 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). 但这不是您可以从错误消息中得到的。

4

1 回答 1

8

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

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

进入哈斯克尔。对于类型化语言，进行上述类型检查的关键是要有一个t与 同构的类型t -> t。在 Haskell 中，这是通过使用newtype关键字来完成的。还有，要产生我们需要的副作用IO，但它不支持callCC。来支持后面我们需要的MonadCont。因此，要与我们需要MonadIO和MonadCont. 此外，newtype必须知道Monad它正在处理哪个，因此它应携带Monad作为其类型参数。所以现在我们写

newtype CFix m = ...

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

由于我们正在研究 a ，因此使用符号Monad很方便。do因此let*作业应翻译为yin <-and yang <-。在我们MonadIO使用. 翻译成但显然我们不能翻译成或类似的东西。让我们暂时搁置一下。displayliftIO.putStrcall-with-current-continuationcallCCid

我的错误是天真地将显示块和callCC块的组合运算符转换为>>=. 在 Scheme 或其他严格的语言中，参数要在表达式之前求值，因此该callCC块应在显示块之前执行。因此，我们将使用=<<代替>>=。代码现在看起来

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签名是

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

所以它的参数有类型

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

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

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

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

以及callCC's 参数的实现

\k -> return (CFix k)

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

现在，我们如何使用yin（类型m (CFix m)）作为函数？类型析构函数goOn允许我们提取内部函数，所以我们有 last 的定义...。

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

这是该程序的最终版本。

于 2013-11-14T04:24:22.053 回答