👨🏼‍⚕️ 📗 ⏰ Erlangで考えて書くことを学ぶ（例として2つの組み合わせ問題を使用） 🧑🏿 🧔 🔽

-...その後、私は彼に銃口を与えます...いいえ、あなたは打ち負かすことはできません！

「問題の事実は、あなたが負けることができないということです」とパニコフスキーは偽善的にため息をつきました。 -ベンダーは許可していません。

I.イルフ、E。ペトロフ。ゴールデンカーフ。

冷淡なブラガは透明な容器に住んでいた

その恐怖さえ強い。彼女はお腹からは好きではない-口から直接

頭に駆け寄り、そこから左右に投げ始めました。

メンタルブレースと拠点の破壊。

M.ウスペンスキー。私たちがいない場所。

おそらく、最初にアーランの勉強を始めた人は誰でも、シュラバラガノフの立場にいると感じているでしょう。 Erlangには、変数を再割り当てし、結果を1つの変数に蓄積するなど、ほとんどの現代言語の概念に馴染みがありません。（公平には、「グローバルな複数変更変数」のErlangスタイルの動作を実装できることに注意してください。このため、各プロセスにはプログラマ定義のキーと値のペアを格納するハッシュディクショナリがあります。組み込み関数put（Key、Value）、get （キー）と他のいくつかの補助関数ですが、アプリケーションでそのような辞書を使用するのは悪いスタイルと見なされ、例外的な場合にのみ推奨されます（ http://www.erlang.org/doc/man/erlang.html\#put-2 ））。結果として、ループ内の反復は、反復変数の値の通常の発生では実装できません。結果の累積は、再帰、および末尾再帰によるサイクルの編成によってのみ実行されます。（もちろん、ループの結果の反復と累積は、リストのライブラリ関数：foreach（関数、リスト）、リスト：foldl（関数、StartValue、リスト）、リスト：foldr（関数、StartValue、リスト）（ http ：//www.erlang.org/doc/man/lists.html ）およびセットの類似物（ http://www.erlang.org/doc/man/sets.html、http://www.erlang.org /doc/man/ordsets.html、http://www.erlang.org/doc/man/gb_sets.html ）および配列（ http://www.erlang.org/doc/man/array.html ）。私たちの目標は、既成のソリューションを使用せずに、サイクルを記述する方法を学ぶことです。そのため、ここではそのようなライブラリの使用を控えます。

したがって、Erlangでは、通常の思考パターンを破り、このプログラミング言語のみに特徴的な新しいパターンに置き換える必要があります。もちろん、理想的な治療法は、すべての「精神的サポートと強化」を破ることができる洗脳です。しかし、私たちにとっては、これはおそらく過激すぎる手段であり、逆の方向に進むでしょう。

聖アンソニー大王の人生には、彼の弟子の一人についての物語があります。弟子が教会に立ち、聖アントニウスが詩salを読んでいるのを聞きました。最初の詩編の最初の詩が鳴るとすぐに：

, ...

学生は神殿を去りました。それ以来、誰も彼を30年近く見ていません。そして、彼が神殿に再び現れたとき、アンソニー大王はなぜ彼をそんなに長く残し、どこに消えたのか尋ねました。弟子は答えました。「父、詩編の言葉を聞いて、荒野に引退して、これらの言葉で言われていることを成し遂げようとしました。邪悪な考えの評議会に行かないでください。」言い換えれば、彼はこれらの言葉から実践的な教訓を学び、今ではさらに読むようになりました。残念ながら、私たちにはそのような時間の余裕はなく、私たちの目標はそれほど高くありません。しかし、基本概念は採用できます。

2つの標準的な組み合わせの問題を検討します。

N個の要素の指定されたセットからすべての可能な順列を検索します
N個の要素の指定されたセットから可能なすべての組み合わせを検索します

Erlangプログラミング言語を使用してそれらを解決するためのさまざまなアプローチと方法を分析し、具体的な例を使用してこの言語のプログラミングの機能を理解し、習得します。

すべての例はcombinat.erlモジュールに収集されており、 https ： //github.com/raven29/combinat_erl.gitで入手できます。

2つの目標-2つの再帰

ソリューションアルゴリズムとして、直接再帰列挙を使用します。これは、再帰の各ステップで実行されることを意味します。

リストからすべての可能な値をループし、これらの各値を既存の結果に追加します。
既に使用されている値が除外される新しいリストの転送を伴う再帰呼び出し。

つまり、この手順は2つの段階で構成されます：再帰の特定のレベルでの巡回検索と次のレベルへの移行。したがって、これらの2つの目標には二重再帰呼び出しが必要です。（アルゴリズムは単純な列挙に基づいているため、最適化が必要です。ただし、最初にその単純さと明確さにより、使用される方法と手法を簡単に説明できるため、検討中の両方の問題に適用されるため、目的に非常に適しています最小限の違いで、適切な比較と類似を行うことができます）。

基本実装

基本機能は、combinat：permuts_out（List、Number）およびcombinat：combs_out（List、Number）関数で実装されます。これらの関数は、それぞれ、リストの要素からのすべての順列およびすべての数値の長さの組み合わせを出力します。以下は、順列を出力するpermuts_out（リスト、数値）関数です。この関数は2回再帰的に呼び出されます。6行目-ループスルー、7行目-次の再帰レベルに移動します。この最後の呼び出しで、結果が変数[RemainH | Result]で増分され、さらに次のレベルの再帰に渡される一般リストからこの結果に含まれる要素が除外されます。 Listの4番目の引数は、順列の場合にのみ剰余を正しく計算するために必要な項目のソースリストです。

 permuts_out(List, Number) -> permuts_out(List, [], Number, List). permuts_out(_Remain, Result, Number, _List) when length(Result) == Number -> io:format("~w~n", [Result]); permuts_out([], _Result, _Number, _List) -> ok; permuts_out([RemainH|RemainT], Result, Number, List) -> permuts_out(RemainT, Result, Number, List), permuts_out(List -- [RemainH|Result], [RemainH|Result], Number, List).

組み合わせの同様の関数は、送信された剰余を計算するためのより単純なルールで、4番目の引数リストがない場合のみ、以前の関数と異なります。

 combs_out(List, Number) -> combs_out(List, [], Number). combs_out(_Remain, Result, Number) when length(Result) == Number -> io:format("~w~n", [Result]); combs_out([], _Result, _Number) -> ok; combs_out([RemainH|RemainT], Result, Number) -> combs_out(RemainT, Result, Number), combs_out(RemainT, [RemainH|Result], Number).

2つの再帰-2つの関数

より明確にするために、2つの再帰呼び出しを2つの異なる関数で表すことができます。関数名の末尾は、それぞれの目的に対応しています。* _iteration-特定の再帰レベルで剰余リストを反復処理するため、* _recursion-次の再帰レベルに移動するため。

 permuts_out_2(List, Number) -> permuts_out_iteration(List, [], Number, List). permuts_out_iteration([], _Result, _Number, _List) -> ok; permuts_out_iteration([RemainH|RemainT], Result, Number, List) -> permuts_out_iteration(RemainT, Result, Number, List), permuts_out_recursion(List -- [RemainH|Result], [RemainH|Result], Number, List). permuts_out_recursion(_Remain, Result, Number, _List) when length(Result) == Number -> io:format("~w~n", [Result]); permuts_out_recursion(Remain, Result, Number, List) -> permuts_out_iteration(Remain, Result, Number, List). combs_out_2(List, Number) -> combs_out_iteration(List, [], Number, List). combs_out_iteration([], _Result, _Number, _List) -> ok; combs_out_iteration([RemainH|RemainT], Result, Number, List) -> combs_out_iteration(RemainT, Result, Number, List), combs_out_recursion(RemainT, [RemainH|Result], Number, List). combs_out_recursion(_Remain, Result, Number, _List) when length(Result) == Number -> io:format("~w~n", [Result]); combs_out_recursion(Remain, Result, Number, List) -> combs_out_iteration(Remain, Result, Number, List).

おそらく、このオプションは過度の煩わしさから、アンチパターンと見なすことができます。

結果を提示してください！

ライブラリ関数を作成する場合、標準ストリームへの出力はほとんど役に立ちません。結果を取得し、それを何らかの形でクライアントコードに渡す必要があります。 Erlangには、結果を蓄積するためのグローバル変数や静的フィールドはありません。代わりに、関数型言語に固有のアプローチを使用できます。

上向き再帰で値を返す
コールバック関数
実行ストリームとストレージストリーム

各オプションを詳細に検討してください。

そこにクマ-戻ってクマ

これまで、関数の本体で何か有用なことを行って（コンピューター画面に結果を表示することが有用であると考えられる場合）、下降再帰に向かっています。逆方向の移動では、関数によって返された結果はまったく使用されませんでした。つまり、上向きの再帰の動きは「空」でした。このアプローチでは、表示されたすべての値をまとめることは不可能です。それらは決して接続されていません。より生産的なのは、再帰を終了するときに関数によって返される結果を使用することです。この場合、再帰関数の最初の呼び出しは、累積結果全体を返すことができます。基本機能の変更は以下のとおりであり、3つのポイントが含まれています。

標準ストリームに出力する代わりに結果[結果]を返す（3行目、11行目）
再帰の下部に、初期値が返されます-okアトムの代わりに空のリスト[]（行4、12）
順次呼び出しの代わりにリスト「++」を合計することによる結果の蓄積（6、14行目）

permuts_res（リスト、数値）およびcombs_res（リスト、数値）関数は、それぞれすべての順列と数値の長さの組み合わせを含むリストのリストを返します。

 permuts_res(List, Number) -> permuts_res(List, [], Number, List). permuts_res(_Remain, Result, Number, _List) when length(Result) == Number -> [Result]; permuts_res([], _Result, _Number, _List) -> []; permuts_res([RemainH|RemainT], Result, Number, List) -> permuts_res(RemainT, Result, Number, List) ++ permuts_res(List -- [RemainH|Result], [RemainH|Result], Number, List). combs_res(List, Number) -> combs_res(List, [], Number). combs_res(_Remain, Result, Number) when length(Result) == Number -> [Result]; combs_res([], _Result, _Number) -> []; combs_res([RemainH|RemainT], Result, Number) -> combs_res(RemainT, Result, Number) ++ combs_res(RemainT, [RemainH|Result], Number).

そして彼と一緒に好きなことをしてください！

1つのコレクション変数に結果を蓄積するのではなく、作成直後に各要素で何か便利なことを行うと便利な場合があります。このアプローチにより、生産性を向上させ、メモリ消費を大幅に削減できます。追加の引数として渡されるコールバック関数を使用して実装できます。関連するオプションを以下にリストします。

 permuts_clb(List, Number, Callback) -> permuts_clb(List, [], Number, List, Callback). permuts_clb(_Remain, Result, Number, _List, Callback) when length(Result) == Number -> Callback(Result); permuts_clb([], _Result, _Number, _List, _Callback) -> ok; permuts_clb([RemainH|RemainT], Result, Number, List, Callback) -> permuts_clb(RemainT, Result, Number, List, Callback), permuts_clb(List -- [RemainH|Result], [RemainH|Result], Number, List, Callback). combs_clb(List, Number, Callback) -> combs_clb(List, [], Number, Callback). combs_clb(_Remain, Result, Number, Callback) when length(Result) == Number -> Callback(Result); combs_clb([], _Result, _Number, _Callback) -> ok; combs_clb([RemainH|RemainT], Result, Number, Callback) -> combs_clb(RemainT, Result, Number, Callback), combs_clb(RemainT, [RemainH|Result], Number, Callback).

Callback変数では、1つの引数からの関数の名前を渡すことができます（アーラン1-アーランの用語によると）。したがって、たとえば、要素[1,2,3] 2のすべての順列を印刷するために呼び出すことができます。

 combinat:permuts_clb([1,2,3], 2, fun(X)->io:format("~w~n",[X]) end).

コールバック関数のより意味のあるアプリケーションについては、次のセクションで説明します。

ビッグブラザーはあなたを見ています

Erlangでの分岐再帰の結果の累積を実装する別の方法は、2つのスレッドを使用することです。 1つのスレッドがエグゼキューターであり、プログラムが実行されます。別のスレッドはオブザーバーであり、再帰関数が結果を渡します。実行中のスレッドが作業を完了すると、監視スレッドは合計結果を表示します。重要：実行スレッドとして、erlシェルが実行されているメインスレッド（スーパーバイザー）を使用できません。このスレッドは、プログラムの実行後に破棄されません。 erlアプリケーションがアンロードされるまで存在し続けます。

以下は、対応する実装です。 3行目は「梯子の出口」を設定します。これにより、正常に完了した場合でも、関連するプロセスからのメッセージの送信が保証されます。デフォルトでは、trap_exitフラグはfalseに設定されています。これは、異常終了が発生した場合にのみ、関連するプロセスからメッセージを受信することを意味します。 5行目では、実行中のスレッドが開始（および同時にバインド）します。このスレッドでは、permuts_clb（またはcombs_clb）関数が起動され、引数List、Number、および各ユニットの結果をオブザーバープロセスに渡すCallbackコールバック関数を受け取ります。

 fun(R)->Supervisor!R end

6行目では、ループ（[]）関数は合計結果の空の初期値で開始します。この関数は、実行中のストリームからのメッセージをリッスンします。次の結果を受信すると、ループ（Total ++ [Result]）が再帰的に呼び出され（14行目）、引数に実行中のストリームから新しく到着した結果が追加されます。実行中のスレッドの作業が完了すると、「ラダーによる終了」が発生します。特殊タイプのタプル（10行目）がループ（）に渡され、パターンマッチングの結果として、全体の結果が表示され（11行目）、実行ストリームとの接続が切断されます（12行目））スーパーバイザー-オブザーバースレッドのpid、ワーカー-エグゼキュータースレッドのpid。

 %% Function = permuts_clb | combs_clb proc(Function, List, Number) -> process_flag(trap_exit, true), Supervisor = self(), spawn_link(combinat, Function, [List, Number, fun(R)->Supervisor!R end]), loop([]). loop(Total) -> receive {'EXIT', Worker, normal} -> io:format("~w~n", [Total]), unlink(Worker); Result -> loop(Total ++ [Result]) end.

この関数は、解決されるタスクに応じて、permuts_clbまたはcombs_clbを最初の引数として呼び出します。たとえば、要素[1,2,3]からのすべての順列の2による出力は、呼び出しによって行われます。

 combinat:proc(permuts_clb, [1,2,3], 2).

初心者に典型的なエラーがあるかもしれません。まず、spawn_link（）の前にloop（）を実行できません。実行スレッドが開始される前に起動されたリスナー関数は、おそらくこのスレッドからの単一のメッセージを見逃さないため、これはより信頼性が高いと思われます。しかし、その結果、プロセスはループ（）でハングし、次の行は呼び出されません。次に、スーパーバイザー変数を使用してオブザーバースレッドにメッセージを送信することが必須です。

 self()!R

実行中のストリームで呼び出されるとself（）関数が実行され、それに応じて実行中のストリームのpidを受け入れるため、動作しません。これらのコメントに対する建設的な批判をしてくれたw495とEvilBlueBeaverに感謝します（そしてそれを理解するのを助けてくれただけです）。

そしてもう1つ小さなコメント：proc（）関数を試すと、さまざまな奇妙なことが起こります。たとえば、関数が「遅延」を伴う結果を生成し始める場合があります。各呼び出しで、前の呼び出しの結果を返します。これは、メインスレッドをオブザーバースレッドとして起動しているためである可能性があります。したがって、障害が発生すると、次のloop（）の呼び出しは、最後の呼び出し（存在する場合）からのすべてのメッセージを最初に処理します。この意味で、spawn（）またはspawn_link（）関数によって生成された別のストリームにもリスナーストリームを実装する方が信頼性が高くなります。

理解することは、有効にすることです

一部のプログラミング言語には、「リスト内包表記」と呼ばれる構文構成体があります。これにより、コンパクトでエレガントな形式でリストの反復走査を指定でき、その結果、新しいリストが生成されます。その結果、元のリストの各要素に関数を適用することにより、各要素が元のリストから取得されます。この設計は、数学的集合論の表記法に基づいています。ここで、たとえば、リスト内包構文では、1から9までのすべての整数の2乗の出力は次のようになります。

 [X*X || X <- [1,2,3,4,5,6,7,8,9]].

リスト内包表記では、複数のリストを渡して条件を課すこともできます。例として、1から9までの乗算テーブルの出力を考えます。

 [io:format("~w * ~w = ~w~n", [I, J, I*J]) || I <- [1,2,3,4,5,6,7,8,9], J <- [1,2,3,4,5,6,7,8,9]].

因子の順列を伴う反復結果が除外されている乗算表：

 [io:format("~w * ~w = ~w~n", [I, J, I*J]) || I <- [1,2,3,4,5,6,7,8,9], J <- [1,2,3,4,5,6,7,8,9], I < J].

ロシア文学では、「リストの理解」は「リストの包含」、「リスト生成」と翻訳されます。翻訳「理解」の主な意味は「理解する」、「理解する」です。だから、英語で理解することは含めることです。

理解構造はリストだけでなく、他のタイプのコレクションにも存在することに注意してください。 Erlangにはリスト内包表記とバイナリ内包表記があります。

その種の中で最もエレガントな

リスト内包構造では、リストの反復走査を指定できます。その結果、基本関数は次の形式を取ります。

 permuts_comp(List, Number) -> permuts_comp(List, [], Number). permuts_comp(_Remain, Result, Number) when length(Result) == Number -> io:format("~w~n", [Result]); permuts_comp(Remain, Result, Number) -> [permuts_comp(Remain -- [R], [R] ++ Result, Number) || R <- Remain].

permuts_comp関数は、リスト内包表記から自身を再帰的に呼び出します。

これはおそらく、最もエレガントな置換関数です。

できないが、本当にしたい場合...

残念ながら、以前の結果を組み合わせの関数に一般化することはそれほど明白ではありません。実際、この場合のリスト内包表記では、リスト全体ではなく、前の呼び出しからの番号によって決定される残りのみを転送する必要があります。リストの代わりに配列があれば、目的のインデックスを簡単に計算できます。しかし、配列は基本的なErlang型ではありません。アレイライブラリを使用するか、アレイを手動で整理します。

これは非常に簡単であることがわかり、対応する実装を以下に示します。元のリストからListIndexedタプルのリストを作成します。各要素には元のリストの要素と整数インデックスが含まれます（2行目）。関数リスト：標準リストモジュールのzip（リスト1、リスト2）は、このような変換に適しています。結果を出力するとき、lists：unzip（ListIndexed）関数を使用します。この関数は、インデックスなしの元の外観のインデックス付きリストを返します（5行目）。そして最も重要なこと-リスト内包表記では、反復に含まれるインデックスに必要な制限を簡単に指定できるようになりました（11行目）。

 combs_comp(List, Number) -> ListIndexed = lists:zip(List, lists:seq(1, length(List))), combs_comp(ListIndexed, [], Number). combs_comp(_Remain, Result, Number) when length(Result) == Number -> {ResultValue, _I} = lists:unzip(Result), io:format("~w~n", [ResultValue]); combs_comp(Remain, [], Number) -> [combs_comp(Remain -- [R], [R], Number) || R <- Remain]; combs_comp(Remain, [{HValue,HIndex}|T], Number) -> [combs_comp(Remain -- [{R,I}], [{R,I}] ++ [{HValue,HIndex}|T], Number) || {R,I} <- Remain, I > HIndex].

それはやや厄介に見え、これはライブラリ関数リストに頼らなければならなかった私たちの例の中で唯一のプログラムです：zip（List1、List2）、リスト：unzip（ListTuple）、リスト：seq（StartValue、Length）。この試みは、アンチパターンの例と考えることもできます。手元のタスクでは、配列モジュールを使用する方が一貫性がありますが、これは別の話になります...

Erlangで考えて書くことを学ぶ（例として2つの組み合わせ問題を使用）