0

昨日の質問Erlangのフォローアップとして：再帰を使用してリストから一意のアイテムを選択する

Erlangで、特定のリストからすべての一意のアイテムを選択したいとします。

List = [foo, bar, buzz, foo].

そして私はあなたのコード例を使用しました

NewList = [bar, buzz].

NewListErlangでさらに操作するにはどうすればよいですか？

たとえば、からすべての一意のアイテムを選択したいだけでなく、 ？Listから結果として得られたすべてのアイテムの合計文字数もカウントしたいとします。NewList

4

3 に答える 3

5

関数型プログラミングでは、非常に頻繁に発生するパターンがあり、それらは独自の名前とサポート機能に値します。最も広く使用されているものの2つはとmap（fold時々reduce）です。これらの2つは、リスト操作の基本的な構成要素を形成し、多くの場合、専用の再帰関数を作成する必要がなくなります。

地図

関数はmapリストを順番に繰り返し、各要素が元のリストの対応する要素に関数を適用した結果である新しいリストを生成します。典型的なmap実装方法は次のとおりです。

map(Fun, [H|T]) -> % recursive case
    [Fun(H)|map(Fun, T)];
map(_Fun, []) -> % base case
    [].

これは、再帰関数の完全な入門例です。大まかに言えば、関数句は再帰的なケース（問題のインスタンスが小さいiselfへの呼び出しになります）または基本的なケース（再帰的な呼び出しは行われません）のいずれかです。

では、どのように使用しますmapか？最初の引数、Funは関数であることに注意してください。Erlangでは、無名関数（ラムダと呼ばれることもあります）をインラインで宣言することができます。たとえば、リスト内の各数値を2乗して、2乗のリストを生成するには、次のようにします。

map(fun(X) -> X*X end, [1,2,3]). % => [1,4,9]

これは高次プログラミングの例です。

mapはErlang標準ライブラリの一部であることに注意してくださいlists:map/2。

折り畳み

mapあるリストと別のリストの間に1：1の要素マッピングを作成するのに対し、目的はfold、合計などの単一の結果を累積しながら、リストの各要素に何らかの関数を適用することです。右の折り目（「右に行く」と考えると役立ちます）は次のようになります。

foldr(Fun, Acc, [H|T]) -> % recursive case
    foldr(Fun, Fun(H, Acc), T);
foldr(_Fun, Acc, []) -> % base case
    Acc.

この関数を使用して、リストの要素を合計できます。

foldr(fun(X, Sum) -> Sum + X, 0, [1,2,3,4,5]). %% => 15

モジュール内のfoldrとfoldlは両方ともErlang標準ライブラリの一部であることに注意してください。lists

mapすぐには明らかではないかもしれませんが、非常に大きなクラスの一般的なリスト操作の問題は、fold単独で使用して解決できます。

再帰的に考える

再帰的アルゴリズムを書くことは最初は気が遠くなるように思えるかもしれませんが、それに慣れるにつれて、それは非常に自然であることがわかります。問題が発生した場合は、次の2つのことを特定する必要があります。

  1. 問題をより小さなインスタンスに分解するにはどうすればよいですか？再帰が役立つためには、再帰呼び出しはその引数としてより小さな問題をとらなければなりません。さもないと、関数は決して終了しません。
  2. 基本的なケース、つまり終了基準は何ですか？

1）については、リストの要素を数える問題を考えてみましょう。これをどのようにして小さなサブ問題に分解できるでしょうか。さて、次のように考えてください。最初の要素（ヘッド）がXで、余り（テール）がYである空でないリストが与えられた場合、その長さは1+Yの長さです。Yはリストよりも小さいため[X | Y]、問題を減らすことに成功しました。

リストの例を続けると、いつ停止しますか？まあ、最終的には、尻尾は空になります。空のリストの長さがゼロであるという定義である基本ケースにフォールバックします。さまざまな場合の関数句の記述は、辞書の定義の記述と非常によく似ていることがわかります。

%% Definition:
%% The length of a list whose head is H and whose tail is T is
%% 1 + the length of T.
length([H|T]) ->
    1 + length(T);
%% Definition: The length of the empty list ([]) is zero.
length([]) ->
    0.
于 2013-03-14T23:23:30.813 に答える
2

折り畳みを使用して、結果のリストを再帰することができます。簡単にするために、アトムを文字列に変換しました (list_to_atom/1 でこれを行うことができます):

1> NewList = ["bar", "buzz"].
["bar","buzz"]
2> L = lists:foldl(fun (W, Acc) -> [{W, length(W)}|Acc] end, [], NewList).        
[{"buzz",4},{"bar",3}]

これは、次のようにアクセスできる proplist を返します。

3> proplists:get_value("buzz", L).
4
于 2013-03-14T20:05:58.613 に答える
0

リストを使用する代わりに、教訓的な目的で自分で再帰を作成する場合は、次のようにします。

count_char_in_list([], Count) ->
    Count;
count_char_in_list([Head | Tail], Count) ->
    count_char_in_list(Tail, Count + length(Head)). % a string is just a list of numbers

その後：

1> test:count_char_in_list(["bar", "buzz"], 0).
7
于 2013-03-14T20:36:48.480 に答える