Clever Geek Handbook

C ++でモナドを使用します。 パート1：モナドのリスト

パート1

パート2



C ++プログラマーは、モナドを使用しないと解決できない問題の例を求めることがあります。 そもそも、この質問はそれ自体では正しくありません。サイクルなしでは解決できない問題があるかどうかを尋ねるのと同じです。 ご使用の言語でgoto演算子がサポートされている場合は、ループステートメントを使用せずに実行できます。 モナド（およびループ）ができることは、コードを単純化し、構造を改善することです。 ループを使用するとスパゲッティコードが通常に変わるため、モナドを使用すると命令型コードを宣言型コードに変換できます。 この変換により、コードをより簡単に記述、理解、保守、および拡張することができます。



さて、インタビューに巻き込まれるかもしれないあなたのためのパズルがあります。 それは完全に些細なことではなく、解決策へのいくつかのアプローチが可能であり、それらの最高のものはすぐには明らかではありません-ただ考えてみてください。

次のパズルに招待されます。 



send + more --------- money




各文字は0から9までの数字に対応しています。書かれた加算操作が正しいように、そのような対応を選択するプログラムを書く必要があります。 記事を読み続ける前に、この問題をどのように解決しますか？



分析





問題を正しく分類することで、インタビュアーにあなたの知識を印象付けることは決して痛いことはありません。 このタスクは、「 制約充足問題 」のクラスに属します。 明らかな制限は、文字を追加する場合、文字の代わりに数字を使用して取得した数字が、指定された数字に対応する数字になることです。 明らかな制限はあまりありません。たとえば、被加数はゼロから始めてはいけません。



ペンと紙でこの問題を解決しようとすると、いくつかのヒューリスティックがすぐに見つかります。 例えば、 mが1に等しくなければならないことはすぐに明らかです。4桁の数字を追加すると、19998より大きい数字が得られないためです。その後、 sが8または9に等しくなければならないことがわかります。放電を転送して5桁の数字を取得するなど。 十分な時間があれば、この問題（および他の類似のルール）を解決できる十分な数のルールを持つエキスパートシステムを作成できます。 ちなみに、エキスパートシステムに言及すると、インタビューでいくつかの追加のポイントを得ることができます。



別のアプローチがあります-タスクのディメンションがかなり小さいことに注意する価値があります-あまり多くない4〜5桁の整数を使用します。 インタビュアーは、整理する必要がある順列の数を尋ねるようにあなたに尋ねるかもしれません-10があります！/（10-8）！ = 1814400個。 現代のコンピューターにはかなり少々。 したがって、問題の解決策は、これらの順列を生成し、元の問題の制約に準拠しているかどうかをチェックすることになります。



額ソリューション





古典的な命令型アプローチは、8つのネストされたループ（ e、n、d、m、o、r、yの 8つの一意の文字があります）を含むコードをすぐに生成します。 次のようになります。 



 for (int s = 0; s < 10; ++s) for (int e = 0; e < 10; ++e) for (int n = 0; n < 10; ++n) for (int d = 0; d < 10; ++d) ...




そして、ここで状態を確認する必要があります。 しかし、元の問題からの合計の条件ではありません-最初に確認する必要があるのは、順列のすべての数値が異なることです。それ以外の場合は意味がありません。 



 e != s n != s && n != e d != s && d != e && d != n


...

など、最後の行には7つの比較があり、合計で28の比較があります。 そしてその後のみ、数字から「 送信 」、「 詳細 」の数字を収集し、合計が「 お金 」かどうかを確認することができます 。



一般に、問題は解決され、インタビュアーは何が悪いのかを言うことができなくなります。 しかし、ちょっと待ってください-もっと良いものを考え出すことはできませんか？



スマートな決定



続行する前に、さらに記述されるものはすべて、Justin Le blogで書かれたプログラムのHaskellからのほぼ直接的な翻訳であると言わなければなりません。 Haskellを研究し、オリジナルの同様の記事を読むことを強くお勧めします。この場合、翻訳者として働きます。



「正面」ソリューションの問題は、これらの28のチェックにあります。 はい、私たちのプログラムは機能しましたが、それは小さな次元のために起こりました。 巨大な次元と非常に多くの条件に問題があるため、それらを解決するための何らかの一般的なアプローチを考え出すのは理にかなっています。



問題は、2つの小さな問題の組み合わせとして定式化できます。 それらの1つは深さに関するもので、2つ目はソリューションの検索の幅に関するものです。



最初に深さの問題を見てみましょう。 元のパズルの文字の代わりに、数字の置換を1つだけ作成するタスクを想像してください。 これは、リスト0、1、... 9から一度に1桁ずつ8桁を選択すると説明できます。 番号が選択されるとすぐに、リストから削除します。 リストをコードにハードドライブしたくないので、アルゴリズムのパラメーターにします。 このアプローチでは、アルゴリズムが重複するリストや、要素に対して比較演算子と等価演算子を定義できないリスト（たとえば、 std :: futureのリスト）でも機能することに注意してください。



次に、幅の問題を見てみましょう。すべての可能な順列に対して上記のプロセスを繰り返す必要があります。 これは、上記のコードの8つのネストされたループが行うこととまったく同じです。 1つの問題があります。リストから次の要素を選択する各ステップは破壊的です-リストを変更します。 これは、ソリューションスペースを列挙する際の既知の問題であり、その標準ソリューションはバックトラッキングです。 候補を処理したら、アイテムをリストに戻し、次のアイテムを試します。 つまり、現在の状態を、暗黙的に関数呼び出しのスタックに保存するか、何らかのデータ構造に明示的に保存する必要があります。



ちょっと待って！ 関数型プログラミングについて話しませんか？ では、なぜこれらすべてが修正と状態について話すのでしょうか？ さて、誰が関数型プログラミングの状態を持てないと言ったのでしょうか？ 関数型言語のプログラマーは、恐竜が地球を歩いたときから状態モナドを使用しています。 また、永続的なデータ構造を使用する場合、変更は問題になりません。 シートベルトを締めて、椅子を垂直位置に戻し、離陸します。



リストモナド





量子力学への小さな言及から始めます。 学校で覚えているように、量子プロセスは決定論的ではありません。 同じ実験を数回行い、それぞれの場合で異なる結果を得ることができます。 量子力学には非常に興味深い視点があり、「 多世界解釈 」と呼ばれます。各実験はいくつかの代替の歴史的行を生成し、それぞれが結果を出し、これらの「宇宙」の1つに陥り、特定の1つを観察します（事前に不明）実験の結果。



同じアプローチを使用してパズルを解きます。 文字に対応する数字の順列ごとに「代替ユニバース」を作成します。 したがって、文字sの 10個のユニバースから開始します。最初の値は0、2番目の値は1、などになります。 さらに、これらの各宇宙を文字eなどで別の10で割ります。 これらの宇宙のほとんどは私たちの条件を満たさないので、それらを破壊することを余儀なくされます。 宇宙の破壊に対するこのような単純なアプローチは、無駄が多くリソースを消費するように思えるかもしれませんが、関数型プログラミングではこれは問題ではありません。 これは、新しいユニバースが生成元のユニバースとそれほど変わらず、ほとんどのデータを「親」で使用できるためです。 これは永続的なデータ構造の考え方です。 クローンを作成することで新しいデータ構造を生成できる不変のデータ構造があります。 新しいデータ構造は、小さな「デルタ」を除いて、ほとんどのデータを親と共有します。 この投稿で説明されている永続リストを使用します。



「複数のユニバース」でこのアプローチを実現すると、実装は非常に簡単になります。 まず、新しいユニバースを作成する関数が必要です。 「安く」することに同意したため、異なる部分のみを生成します。 変数sによって生成されるすべてのユニバースの違いは何ですか？ s変数の値のみ。 合計で、0から9までのs値に対応する10個のそのようなユニバースがあります（ sを0に等しくすることができないという事実は、後で考慮されます）。 したがって、必要なのは10桁のリストを生成する関数だけです。 さて、ここにあります-すべての純粋な原始的な美しさで私たちの10の宇宙。



そして今、私たちはこれらの代替宇宙の1つに自分自身を見つけます（実際には一度にすべてですが、今私たちはそれらの1つに入ることを検討しています）。 どうにか生き続けなければなりません 関数型プログラミングでは、残りの人生はContinuationという関数の呼び出しです。 これはひどい単純化のように聞こえます。 すべてのアクション、感情、希望は、1つの関数を呼び出すだけです。 さて、「継続」は、この宇宙でのあなたの人生の一部、その「計算」コンポーネント、および他のすべてが別々にどこかで起こると考えてみましょう。



それでは、この宇宙での私たちの人生は何に帰着し、何をもたらしますか？ 入力はユニバース自体です。特にこの例では、このユニバースを作成するときに選択したsの値の1つです。 しかし、私たちは量子実験の空間に住んでいるので、出力は一連の新しい宇宙になります。 したがって、「継続」は入力として数値を受け取り、リストを生成します。 これは必ずしも数字のリストではなく、生成されたユニバースの相互の違いを説明する何かのリストです。



さて、この新しいアプローチのポイントは何ですか？ これは、宇宙の選択の「継続」へのリンクです。 これは、すべてのアクションが行われる場所です。 このバインディングも、関数として表現できます。 これは、入力としてユニバースのリストを受け取り、新しいユニバースのリストを生成する「継続」を受け取る関数です（より大きい）。 この関数をfor_eachと呼び、できるだけ一般的に記述しようとします。 送信または生成されるユニバースのタイプについては何も想定していません。 また、「continue」型をテンプレートパラメーターにし、 autoおよびdecltypeを使用して戻り値の型を決定します。 



 template<class A, class F> auto for_each(List<A> lst, F k) -> decltype(k(lst.front())) { using B = decltype(k(lst.front()).front()); // ,    F        , //         ++ static_assert(std::is_convertible< F, std::function<List<B>(A)>>::value, "for_each requires a function type List<B>(A)"); List<List<B>> lstLst = fmap(k, lst); return concatAll(lstLst); }




fmap関数は 、標準std ::変換に似ています-lstリストの各要素に「継続」 kを適用します。 k自体がリストを返すため、結果はリストのリストlstLstになります。 concatAll関数は、これらすべてのリストのすべての要素を1つの大きなリストに結合します。



おめでとうございます！ モナドを見ただけです。 これはリストモナドと呼ばれ、特に非決定的なプロセスのモデリングに使用できます。 モナドは、実際には2つの関数によって定義されます。 それらの1つは上記のfor_eachで、2番目は次のとおりです。 



 template<class A> List<A> yield(A a) { return List<A> (a); }




これは、1つのアイテムのリストを返すyield関数です。 「ユニバースの乗算」をすでに完了した段階でyieldを使用し、単一の値を返したいポイントに到達します。 これを使用して、1つの意味のみを含む「継続」を作成します。 それは完全に前もって決定され、選択の余地のない孤独な退屈な生活を表しています。



これらの関数は、リストモナドだけでなく一般的にモナドを定義するため、 後でこれらの関数の名前をmbindおよびmreturnに変更します。



for_eachやyieldのような名前には、かなり「命令的な」音がします。 これは、もちろん、関数型プログラミングのモナドでは、ある意味で命令型コードの役割を果たすからです。 ただし、 for_eachもyieldもデータ構造ではなく、関数です。 より正確には、ループのように聞こえて動作するfor_eachは、その実装で使用されるfmapのような高階関数です。 もちろん、あるレベルではコードが必須になります。同じfmapを再帰的に、またはループを使用して記述できますが、最上位には関数宣言しかありません。 さて、ここにあります-宣言型プログラミング！



for_eachのように、ループと関数には大きな違いがあります： for_eachはリスト全体を引数として受け取りますが、ループは必要な値（この場合は整数）をその場で生成できます。 Haskellのようなレイジーコンピューティングをサポートする関数型言語では、これは問題ではありません-リストは必要に応じて計算されます。 同様の動作は、ストリームまたは遅延イテレータを使用してC ++で実装できます。 このタスクで扱うリストは比較的短いため、ここではこれを行いませんが、この記事でこのアプローチについて詳しく読むことができます。



パズルの完全なソリューションを作成する準備はまだできていませんが、どのように見えるかについてのスケッチをお見せします。 StateLが単なるリストであると想像してください 。 全体像の意味を見てください： 



 StateL<tuple<int, int, int>> solve() { StateL<int> sel = &select<int>; return for_each(sel, [=](int s) { return for_each(sel, [=](int e) { return for_each(sel, [=](int n) { return for_each(sel, [=](int d) { return for_each(sel, [=](int m) { return for_each(sel, [=](int o) { return for_each(sel, [=](int r) { return for_each(sel, [=](int y) { return yield_if(s != 0 && m != 0, [=]() { int send = asNumber(vector{s, e, n, d}); int more = asNumber(vector{m, o, r, e}); int money = asNumber(vector{m, o, n, e, y}); return yield_if(send + more == money, [=]() { return yield(make_tuple(send, more, money)); }); }); });});});});});});});}); }




for_eachの最初の呼び出しでは、整数のサンプルsel （一意性について考えるまで）を使用し、「continue」は1つの整数sを取得し、ソリューションのリスト（3つの整数のタプル）を生成するラムダ関数です。 この「継続」は、次の文字、eなどの選択とともにfor_eachを順番に呼び出します。



最も内側の「継続」は、 yield_ifと呼ばれるyield関数の条件付きバージョンです。 条件をチェックし、空のリストまたは1つの要素（決定）で構成されるリストを生成します。 内部では、 yield_ifを再度呼び出し、最終的なyieldを呼び出します。 この最終的な収量では、呼び出されたとき（または上記のすべての条件が機能しない場合に機能しない場合）、ソリューションが生成されます-元のパズルの条件を満たすトリプルの数。 複数のソリューションがある場合、それらはすべてfor_each内に作成された結果リストに追加されます。



この一連の記事の第2部では、一意の数値を選択する問題に戻り、状態モナドについて検討します。 githubの最終コードもご覧ください 。



独立した仕事のタスク







More articles:


All Articles