無料のモナドは何がいい

Habrahabrの読者に「なぜ無料のモナドが重要なのか」という記事の翻訳を提供します。

通訳者

優秀なプログラマーは、データとこのデータを処理するインタープリターを共有します。 例としては、ソースコードを抽象構文ツリーとして提示するコンパイラーがあります。これは、多数のインタープリターのいずれかによって後で処理できます。 つまり、次のことができます。

• コンパイルして実行します。
• 従来のインタープリターを使用して直接実行します。
• 圧縮およびアーカイブ;
• ただ彼を放っておいてください。

この分離の利点は明らかです。 構文ツリーの本質を表示する抽象化を構築してみましょう。 特定の例から始めた方が良いでしょう。 これを行うには、独自のおもちゃ言語を設計し、データ型として設計しようとします。



言語には3つのコマンドのみが含まれます。

• 出力b-端末にbを出力
• ベル-システムスピーカーを有効にします
• 完了-実行の終了

これは、後続のコマンドが以前のコマンドのリーフになる構文ツリーとして提示します。

data Toy b next = Output b next | Bell next | Done
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

[完了]コマンドにはシートがないため、端末にする必要があります。

これで、プログラムを作成し、インタープリターで実行できました。

 -- output 'A' -- done Output 'A' Done :: Toy Char (Toy a next)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

しかし、残念ながら、これはうまくいかない悪い決定です。 新しいコマンドがプログラムに追加されるたびに、式のタイプが変更されます。

 -- bell -- output 'A' -- done Bell (Output 'A' Done) :: Toy a (Toy Char (Toy b next))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

幸いなことに、型を維持しながら任意の数のToyインスタンスを使用するために、次のことができます。

 data Cheat f = Cheat (f (Cheat f))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Cheat型は、Doneコンストラクターで終わるファンクターシーケンスを定義します。 驚いたことに、Haskellにはすでに同様のタイプが含まれています。

 data Fix f = Fix (f (Fix f))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Fixは、ファンクターの不動点を意味します。 Fixを装備して、プログラムを書き換えることができます。

 Fix (Output 'A' (Fix Done)) :: Fix (Toy Char) Fix (Bell (Fix (Output 'A' (Fix Done)))) :: Fix (Toy Char)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

現在、両方の式は同じ型です。 素晴らしい。 ただし、このソリューションにはまだ問題があります。ファンクターのチェーンは、Doneコンストラクターによって完了する必要があります。 残念ながら、プログラマーは最初から最後まで自分でプログラムを書くことはあまりありません。 多くの場合、他のプログラムから呼び出すことができるプロシージャを書きたいだけです。 タイプFixはこれを許可しません。



この問題を解決してみましょう。 プロシージャは終了しますが、Doneを呼び出す準備ができていません。代わりに、例外をスローして、呼び出し元のプロシージャがそれを処理して実行を継続できるようにします。

 data FixE fe = Fix (f (FixE fe)) | Throw e
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ハンドラー関数は次のようになります。

 catch (Fucntor f) => FixE f e1 -> (e1 -> FixE f e2) -> FixE f e2 catch (Fix x) f = Fix (fmap (flip catch f) x) catch (Throw e) f = fe
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それを使用するには、ToyをFunctorクラスのインスタンスにする必要があります。

 instance Functor (Toy b) where fmap f (Output x next) = Output x (f next) fmap f (Bell next) = Bell (f next) fmap f Done = Done
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで、実行されるコードを記述し、呼び出し元のプロシージャに制御を返すことができます。

 data IncompleteException = IncompleteException -- output 'A' -- throw IncompleteException subroutine = Fix (Output 'A' (Throw IncompleteException)) :: FixE (Toy Char) IncompleteException -- try {subroutine} -- catch (IncompleteException) { -- bell -- done -- } program = subroutine `catch` (\_ -> Fix (Bell (Fix Done))) :: Fix (Toy Char) e
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

モナド無料。 パート1

「改善された」修正を誇らしげにパッケージ化し、fix-impovedという名前でHackageに公開しました。その後、予想どおりに使用されないことがわかりました。ユーザーは例外ではなく通常の値を渡します。 あえて 例外的な状況の場合のみ例外！ なんておっぱい！

...誰が誰であるかは不明ですが、FixEはすでに実装されており、Freeと呼ばれているためです。

 data Free fr = Free (f (Free fr) instance (Functor f) => Monad (Free f) where return = Pure (Free x) >>= f = Free (fmap (>>= f) x) (Pure r) >>= f = fr
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

returnは私たちのThrowで、（>> =）はcatchです。 ユーザーは、通常の値を渡すために例外を合理的に使用しました。

haskellの優れた点は、モナドでdo記法を自由に使用できることです。 しかし、言語のコマンドでdo記法を使用するには、そのタイプをToy bからFree（Toy b）に変更する必要があります。 次のようになります。

 output :: a -> Free (Toy a) () output x = Free (Output x (Pure ())) bell :: Free (Toy a) () bell = Free (Bell (Pure ())) done :: Free (Toy a) r done = Free Done
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

一般的なパターンに気づきましたか？

 liftF :: (Functor f) => fr -> Free fr liftF command = Free (fmap Pure command) output x = liftF (Output x ()) bell = liftF (Bell ()) done = liftF Done
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで、do-notationを使用してコマンドを順番に実行できます。 前の例を書き直して、不要な例外を取り除きましょう。

 subroutine :: Free (Toy Char) () subroutine = output 'A' program :: Free (Toy Char) r program = do subroutine bell done
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これが魔法の始まりです。 表記法プログラムは、解釈可能な純粋なデータです。 初心者はしばしばモナドを外部効果に関連付けますが、上記のコードはデータのみを生成します。 これらを文字列表現に変換する関数を書くことでこれを示すことができます：

 showProgram :: (Show a, Show r) => Free (Toy a) r -> String showProgram (Free (Output ax)) = "output " ++ show a ++ "\n" ++ showProgram x showProgram (Free (Bell x)) = "bell\n" ++ showProgram x showProgram (Free Done) = "done\n" showProgram (Pure r) = "return " ++ show r ++ "\n"
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そしてそれを実行する

 >>> putStr (showProgram program) output 'A' bell done
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最初の通訳を書いたばかりのようです。 これを使用して、モナドが特定の法律に従っていることを確認できます。

 pretty :: (Show a, Show r) => Free (Toy a) r -> IO () pretty = putStr . showProgram >>> pretty (output 'A') output 'A' return () >>> pretty (return 'A' >>= output) output 'A' return () >>> pretty (output 'A' >>= return) output 'A' return () >>> pretty ((output 'A' >> done) >> output 'C') output 'A' done >>> pretty (output 'A' >> (done >> output 'C')) output 'A' done
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Doneがそれに続くすべてのコマンドを飲み込むことに注意してください。 説明のために、DoneをToyに含めました。 ほとんどの場合、このようなコンストラクターは必要ありませんが、Pureが提供する動作、つまり実行を継続する可能性が必要ですが、例外が存在する場合があります。



伝統的な意味で通訳を書くこともできます：

 ringBell :: IO () -- ,  ,   interpret :: (Show b) => Free (Toy b) r -> IO () interpret (Free (Output bx)) = print b >> interpret x interpret (Free (Bell x)) = ringBell >> interpret x interpret (Free Done ) = return () interpret (Pure r) = throwIO (userError "Improper termination")
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Monad Freeは、どのように使用する場合でも使用できます。

マルチタスク

2つのモナドの「フロー」があり、それらの実装のステップを変更したいとします。 IOモナドの場合、forkIOを並列で実行するだけで使用できますが、StateモナドやContモナドでも同じことを行う必要がある場合はどうでしょうか。 ストリームをモナドのアクションのリストとして提示することができます：

 type Thread m = [m ()]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

...しかし、アクション間で計算の結果を転送する方法がないのと同様に、インタプリタが指定された順序でそれらを呼び出すという保証はありません。 ただし、前のアクションで後続の各アクションをネストし、別のコンストラクターを使用してストリームの終わりを示すことにより、実行順序を保証できます。

 data Thread mr = Atomic (m (Thread mr)) | Return r
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この構造により、現在のアクションが完了した後にのみ次のアクションを取得できます。 これで、個々のモナド呼び出しをアトミックスレッドステップでラップできます。

 atomic :: (Monad m) => ma -> Thread ma atomic m = Atomic $ liftM Return m
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Threadをモナドにする必要があります。2つのストリームを接着するように「ふりをする」が、同時に各ステップの原子性を保持するので、将来、他のスレッドのステップと交互にできるようになります。

 instance (Monad m) => Monad (Thread m) where return = Return (Atomic m) >>= f = Atomic (liftM (>>= f) m) (Return r) >>= f = fr
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これを使用して、アトミックステップで構成されるフローを作成できます。

 thread1 :: Thread IO () thread1 = do atomic $ print 1 atomic $ print 2 thread2 :: Thread IO () thread2 = do str <- atomic $ getLine atomic $ putStrLn str
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

行われなければならないことは、個々のステップの原子性を保持しながら、2つのフローの交互を実現することです。 最も簡単な実装を書きましょう：

 interleave :: (Monad m) => Thread mr -> Thread mr -> Thread mr interleave (Atomic m1) (Atomic m2) = do next1 <- atomic m1 next2 <- atomic m2 interleave next1 next2 interleave t1 (Return _) = t1 interleave (Return _) t2 = t2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、結果のスレッドを実行する方法を学ぶ必要があります。

 runThread :: (Monad m) => Thread mr -> mr runThread (Atomic m) = m >>= runThread runThread (Return r) = return r >>> runThread (interleave thread1 thread2) 1 [[Input: "Hello, world!"]] 2 Hello, world!
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

魔法！ 最も簡単なフロー制御システムを実装しました。 今すぐ純粋な状態のモナドで使用してみてください。

モナド無料。 パート2

気をつけていれば、Threadはベールに包まれたフリーでアトミックなliftFであることに気付くかもしれません。 この例は、自由なモナドとリストがどれだけ近いかを示しています。 実際、FreeとListの定義を比較してください。

 data Free fr = Free (f (Free fr)) | Pure r data List a = Cons a (List a ) | Nil
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

言い換えれば、無料のモナドをファンクターのリストと考えることができます。 FreeコンストラクターはConsのように動作し、ファンクターをリストに追加し、PureはNilのように空のリスト（ファンクターの欠如）を象徴します。



Listが値のリストであり、フリーモナドがファンクターのリストである場合、これらのファンクター自体が値である場合はどうなりますか。

 type List' a = Free ((,) a) () List' a = Free ((,) a) () = Free (a, List' a) | Pure () = Free a (List' a) | Pure ()
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それは普通のリストです。



したがって、リストはFreeモナドの特殊なケースです。 ただし、Monadクラスのインスタンスとしての[]は、List 'a（つまり、Free（（、）a））とは異なります。 リスト 'aで、モナドに結合します（約Pere。：どうやら、バインドを意味します）。これは（++）とreturn-のように動作します[]。 リストのモナドは、do記法を使用して値を連結する珍しい方法と考えることができます。



無料のモナドをリストと考えると、多くのことがより明白になります。 たとえば、liftFは、1つのファンクターを含む無料のモナドを作成する単一の要素を持つリストとして表されます。

 singleton x = Cons x Nii -- x:[]  [x] liftF x = Free (fmap Pure x)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

同様に、インターリーブ関数はリストマージです。

 merge (x1:xs1) (x2:xs2) = x1:x2:merge xs1 xs2 merge xs1 [] = xs1 merge [] xs2 = xs2 --     : -- [x1] ++ [x2] ++ interleave xs1 xs2 interleave (Atomic m1) (Atomic m2) = do next1 <- liftF m1 next2 <- liftF m2 interleave next1 next2 interleave a1 (Return _) = a1 interleave (Return _) a2 = a2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

実際、このように無料のモナドを見ると、マルチタスクはアクションリストの通常のマージのように見えます。 次の出版物では、無料のモナドを使用してエレガントなフロー制御システムとスケジューラーを構築する方法を示す優れた記事をレビューします。



Freeモナドがリストに似ていることは偶然ではありません。 カテゴリ理論を考えると、両方が無料のオブジェクトであり、リストが無料のモノイドであり、無料のモナドが無料のモナドであることを理解できます。

通訳。 継続

最初の部分では、インタプリタで無料のモナドを使用するという概念を紹介しましたが、この考えの可能性は思ったよりもはるかに大きく、コンパイラやフォーマットされた出力に限定されません。 例として、haskellでプログラムする機能を備えたゲームを作成して、0x10cをプレイするという彼のアイデアでNotchを倒すことを決めたとします。 プレイヤーにプログラムの実行を許可したいが、同時にIOモナドへのフルアクセスを制限したい。 あなたの行動は何ですか？



オリジナルのhaskellデザインを使用できます。このデザインでは、出力は外部へのクエリのリストとして提示され、そこから受信した回答のリストとして入力されます。

 main :: [Response] -> [Request]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

タイプRequestは実行可能なすべてのアクションの列挙であり、Responseは結果です。 このゲームでは、クエリのセットは次のようになります。

 data Request = Look Direction | ReadLine | Fire Direction | WriteLine String
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

...および一連の回答：

 data Response= Image Picture --   Look | ChartLine String --   Read | Succeed Bool --   Write
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このアプローチは機能しないと言っても安全です。 リクエストとレスポンスの間に明確な対応はありません（Fireには回答がまったくありません）。リクエストを送信する前に回答を得ようとするとどうなるかは完全に不明です。



これらのタイプを1つに組み合わせて一致させて、これを設定してみましょう。

 data Interaction next = | Look Direction (Image -> next) | Fire Direction next | ReadLine (String -> next | WriteLine String (Bool -> next)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

各コンストラクターには、プレーヤーが入力する必要があるフィールドがあります（クエリパラメーター）。 プレイヤーは、インタープリターが受け取った回答に適用する機能を転送することもできます。 相互作用タイプは、個々のステップごとのプログラマーとインタープリター間の契約と考えることができます。



InteractionをFunctorクラスのインスタンスに簡単に作成できます。

 instance Functor Interaction where: fmap f (Look dir g) = Look dir (f . g) fmap f (Fire dir x) = Fire dir (fx) fmap f (ReadLine g) = ReadLine (f . g) fmap f (WriteLine sg) = WriteLine s (f . g)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

実際に自分で行う必要はありません。 GHCはDeriveFunctor拡張機能を提供します。これにより、次のように簡単に記述できます。

 data Interaction ... deriving (Functor)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、望ましい結果を達成します。

前と同様に、Freeモナドを使用してアクションリストを作成できます。

 type Program = Free Interaction
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このタイプでは、プレーヤーは簡単なプログラムを作成できます。

 easyToAnger = Free $ ReadLine $ \s -> case s of "No" -> Free $ Fire Forward $ Free $ WriteLine "Take that!" (\_ -> easyToAnger) - -> easyToAnger
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで、おそらく仮想のモナドゲームに変換することで、このプログラムを起動できます。

 interpret :: Program r -> Game r interpret prog = case prog of Free (Look dir g) -> do img <- collectImage dir interpret (g img) Free (Fire dir next) -> do sendBullet dir interpret next Free (ReadLine g) -> do str <- getChatLine interpret (g str) Free (WriteLine sg) -> putChatLine s interpret (g True) Pure r -> return r
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Freeモナドを使用しているため、プレーヤーを構文糖衣で扱うことができ、do-notationでプログラムを書くことができます。

 look :: Direction -> Program Image look dir = liftF (Look dir id) fire :: Direction -> Program () fire dir = liftF (Fire dir ()) readLine :: Program String readLine = liftF (ReadLine id) writeLine :: String -> Program Bool writeLine s = liftF (WriteLine s id)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで、プレーヤーがプログラムを作成するのに便利になります。

 easyToAnger :: Program a easyToAnger = forever $ do str <- readLine when (str == "No") $ do fire Forward _ <- writeLine "Take that!" return ()
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

一言で言えば、プレーヤーに可能なアクションを制限するインタラクション言語を提供すると同時に、シンタックスシュガーとハスケルパンを維持します。 プレイヤーのプログラムを完全に解釈する自由がまだあります。 たとえば、明日、ゲームの世界を変えるパッチをリリースする場合（そしてhaskellにはコードをホットスワップするメカニズムがあります）、プレーヤープログラムの実行を中断することなくインタープリターを変更できます。

無料のモナド。 パート3

無料のモナドは、通訳の親友です。 それは可能な限り「インタプリタを解放」し、同時にモナドを維持するために必要な最小値を維持します。



プログラマーにモナドのみを使用できるようにインタープリターを設定するたびに、無料のモナドが助けになります。 あなたが自分をインタプリタとして紹介し、私をプログラマーとして紹介する場合、あなたは代替を選択する権利を留保し、あなたが私に与えた無料のモナドのみを使用してプログラムを書くことを強制します。



可能な限り「インタプリタを解放する」という表現は、次のように言い換えることができる最適化タスクのように聞こえます。



まだモナドである場合、どのモナドが解釈に最も柔軟性があるか



実際、与えられた制限の下で「自由」の概念を詳細に調べると、この概念が形式化されているカテゴリー理論の自由オブジェクトの定義につながります。 自由モナドは「最も自由な」オブジェクトであり、モナドです。