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)を与える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

これを修正するアイデアはありますか？

アップデート

自分で答えを見つけましたが、そのエラーメッセージが何を意味するのかまだわかりません。誰でも私に説明できますか？私がすでに知っていることは、問題のあるバージョンでは、期待される ではなく の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かを知る必要があるため、型パラメーターとして を運ぶ必要があります。だから今、私たちは書きますMonadMonad

newtype CFix m = ...

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

で作業しているので、表記Monadを使用すると便利です。doしたがって、let*代入は および に変換されyin <-ますyang <-。MonadIOtoでは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. これまでに記述されたコードを見ると、と が同じ型のs return valueを持つyinと簡単に結論付けられます。ただし、元のスキーマ バージョンではandを関数として使用しているため、 type があります。したがって、ここで再帰型と が必要になります。yangcallCCm ayinyangp -> rnewtype

単純な方法を取得するm aには usereturnが必要であり、 type を持つものが必要ですa。これがこれから定義しようとしている型コンストラクターから来ているとしましょう。パラメータを提供するには、 fromcallCCを構築する必要があります。したがって、コンストラクタは次のようになります。しかし、何ですか？簡単な選択は、同じ を使用することです。したがって、次の定義があります。a(a -> m b)baCFix

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

およびcallCCのパラメータの実装

\k -> return (CFix k)

コンストラクターを使用して指定されたパラメーターからCFixを構築し、 を使用して目的の型にラップします。CFixreturn

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 に答える