Haskell Language
無料のMonads

フリーモナドは、モナド計算をデータ構造とインタプリタに分割します。

例えば、プロンプトから読み書きするコマンドを含む計算：

まず、Functorのデータ型としての計算の「コマンド」について説明します

{-# LANGUAGE DeriveFunctor #-}

data TeletypeF next
    = PrintLine String next
    | ReadLine (String -> next)
    deriving Functor

次にFreeを使用して「Free Monad over TeletypeF 」を作成し、いくつかの基本操作を作成します。

import Control.Monad.Free (Free, liftF, iterM)

type Teletype = Free TeletypeF

printLine :: String -> Teletype ()
printLine str = liftF (PrintLine str ())

readLine :: Teletype String
readLine = liftF (ReadLine id)

fがFunctorであるときは、 Free fはMonadので、標準Monad （ do notationを含む）を使ってTeletype計算を構築することができます。

import Control.Monad -- we can use the standard combinators

echo :: Teletype ()
echo = readLine >>= printLine

mockingbird :: Teletype a
mockingbird = forever echo

最後に、 Teletype a価値のあるものに変える「通訳」を書いて、私たちはIO aように働く方法を知っています。

interpretTeletype :: Teletype a -> IO a
interpretTeletype = foldFree run where
  run :: TeletypeF a -> IO a
  run (PrintLine str x) = putStrLn *> return x
  run (ReadLine f) = fmap f getLine

Teletype aをIO計算を「実行」するために使用できるもの

> interpretTeletype mockingbird
hello
hello
goodbye
goodbye
this will go on forever
this will go on forever

無料のMonadsは固定小数点のようです

Freeの定義とFixの定義を比較する：

data Free f a = Return a
              | Free (f (Free f a))

newtype Fix f = Fix { unFix :: f (Fix f) }

特に、 Freeコンストラクタの型とFixコンストラクタの型を比較します。 Free Fixと同様のファンクタがありますが、 Freeには別のReturn a caseがあります。

foldFreeとiterMはどのように機能しますか？

iterM :: (Functor f, Monad m) => (f (ma) -> ma) -> (Free fa -> ma) : iterM :: (Functor f, Monad m) => (f (ma) -> ma) -> (Free fa -> ma)とfoldFree :: Monad m => (forall x. fx -> mx) -> (Free fa -> ma) iterM :: (Functor f, Monad m) => (f (ma) -> ma) -> (Free fa -> ma)をfoldFree :: Monad m => (forall x. fx -> mx) -> (Free fa -> ma)て、 Free計算を別のモナドm解釈することによってiterM :: (Functor f, Monad m) => (f (ma) -> ma) -> (Free fa -> ma) foldFree :: Monad m => (forall x. fx -> mx) -> (Free fa -> ma)彼らは何をしていますか？

まずTeletype a関数をIO手動で解釈させるために必要なことを見てみましょう。 Free faが定義されていると見ることができます

data Free f a 
    = Pure a 
    | Free (f (Free f a))

Pureケースは簡単です：

interpretTeletype :: Teletype a -> IO a
interpretTeletype (Pure x) = return x
interpretTeletype (Free teletypeF) = _

では、 FreeコンストラクタでビルドされたTeletype計算をどのように解釈するのですか？ teletypeF :: TeletypeF (Teletype a)調べてIO a型の値に到達したいと考えています。まず、 runIO :: TeletypeF a -> IO aの1つのレイヤーをIOアクションにマッピングする関数runIO :: TeletypeF a -> IO aを記述します。

runIO :: TeletypeF a -> IO a
runIO (PrintLine msg x) = putStrLn msg *> return x
runIO (ReadLine k) = fmap k getLine

これで、 runIOを使用して残りのinterpretTeletypeを記入することができます。 teletypeF :: TeletypeF (Teletype a)は、残りのFree計算を含むTeletypeFファンクタの層であることを思い出してください。私たちはrunIOを使って最外層を解釈します（ runIO teletypeF :: IO (Teletype a)を持っていrunIO teletypeF :: IO (Teletype a) ）。そして、 IOモナドの>>=コンビネータを使って返されたTeletype aを解釈します。

interpretTeletype :: Teletype a -> IO a
interpretTeletype (Pure x) = return x
interpretTeletype (Free teletypeF) = runIO teletypeF >>= interpretTeletype

定義foldFreeまさにそれのあるinterpretTeletypeことを除いて、 runIO機能は、因数分解されています。その結果、 foldFreeは、特定のベースファンクタとターゲットモナドとは独立して動作します。

foldFree :: Monad m => (forall x. f x -> m x) -> Free f a -> m a
foldFree eta (Pure x) = return x
foldFree eta (Free fa) = eta fa >>= foldFree eta

foldFreeはランク2型です： etaは自然な変換です。 foldFree与えられたMonad m => (f (Free fa) -> m (Free fa)) -> Free fa -> maであるが、 f層内のFree計算を検査する自由をetaに与える。 foldFree与えるfoldFreeこのより制限的なタイプは、 etaが一度に1つのレイヤーしか処理できないようにします。

iterMは、折り畳み関数にサブ計算を検査する機能を与えます。以前の反復の（モナド）結果は、 fのパラメータの中の次のもので利用できます。 iterMに類似してparamorphism一方foldFree似ているcatamorphism 。

iterM :: (Monad m, Functor f) => (f (m a) -> m a) -> Free f a -> m a
iterM phi (Pure x) = return x
iterM phi (Free fa) = phi (fmap (iterM phi) fa)

フリーヤーモナド

Freer（またはPrompt、Operational）モナドと呼ばれるフリーモナドの代替策があります。 Freerモナドは、基礎となる命令セットのためのFunctorインスタンスを必要とせず、標準フリーモナドよりもはっきりとリストのような構造を持っています。

Freerモナドは、プログラムを命令セットi :: * -> *属するアトミック命令のシーケンスとして表します。各命令は、そのパラメータを使用して戻り値の型を宣言します。たとえば、 Stateモナドの基本命令セットは次のとおりです。

data StateI s a where
    Get :: StateI s s  -- the Get instruction returns a value of type 's'
    Put :: s -> StateI s ()  -- the Put instruction contains an 's' as an argument and returns ()

これらの命令をシーケンシングするには、 :>>=コンストラクタを使用します。 :>>=を返す単一の命令取りaし、継続にその戻り値配管、プログラムの残りの部分にそれを付加します。換言すれば、復帰命令所与a 、そしてオンにする機能a返すプログラムにb 、 :>>=復帰プログラム産生するb 。

data Freer i a where
    Return :: a -> Freer i a
    (:>>=) :: i a -> (a -> Freer i b) -> Freer i b

aは、 :>>=コンストラクタで存在するように数量化されていることに注意しaください。通訳者は、GADT iパターンマッチングによってa何が何でaかを知る唯一の方法があります。

そもそも 、共ヨナの補題はFreerがFree同形であることを私たちに伝えています。 CoYonedaファンクタの定義を思い出してください：

data CoYoneda i b where
  CoYoneda :: i a -> (a -> b) -> CoYoneda i b

Freer iはFree (CoYoneda i)と同等です。 Freeのコンストラクタをf ~ CoYoneda iを設定すると、次のようになります。

Pure :: a -> Free (CoYoneda i) a
Free :: CoYoneda i (Free (CoYoneda i) b) -> Free (CoYonda i) b ~
        i a -> (a -> Free (CoYoneda i) b) -> Free (CoYoneda i) b

そこから私たちは回復できるFreer iだけで設定することでのコンストラクタをFreer i ~ Free (CoYoneda i) 。

のでCoYoneda iあるFunctor任意のためi 、 FreerあるMonad任意のためiも、 iないですFunctor 。

instance Monad (Freer i) where
    return = Return
    Return x >>= f = f x
    (i :>>= g) >>= f = i :>>= fmap (>>= f) g  -- using `(->) r`'s instance of Functor, so fmap = (.)

あるハンドラのモナドに命令をマッピングすることで、 Freer用にインタプリタを構築することができます。

foldFreer :: Monad m => (forall x. i x -> m x) -> Freer i a -> m a
foldFreer eta (Return x) = return x
foldFreer eta (i :>>= f) = eta i >>= (foldFreer eta . f)

たとえば、通常のState sモナドをハンドラとして使用してFreer (StateI s)モナドを解釈できます。

runFreerState :: Freer (StateI s) a -> s -> (a, s)
runFreerState = State.runState . foldFreer toState
    where toState :: StateI s a -> State s a
          toState Get = State.get
          toState (Put x) = State.put x