Haskell版阴阳拼图:种类不兼容错误

Question

我想在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是类型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

有什么想法解决这个问题？

UPDATE

虽然我自己找到了答案,但我仍然不明白该错误信息的含义.任何人都可以向我解释一下吗？我所知道的是,在有问题的版本中,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等.我们暂时离开吧.

我的错误是天真地将显示块和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.但是,原始模式版本使用yin和yang作为函数,因此它们具有类型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参数的实现

\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

这是该计划的最终版本.