erlang - 查找元组列表中的所有元组

问题描述

我目前正在攻读计算机科学硕士学位的第二个学期，并正在学习分布式系统编程课程。因此，我们应该提交每周练习，其中还包括在 Erlang 中的编码练习。

由于这是课程的第二周，我们才刚刚开始使用 Erlang，这是第一个练习，我们应该在一个模块中实现 6 个函数。前 5 个功能我自己可以轻松完成，但第 6 个功能完全让我不知所措。为此，我们应该编写一个接受 2 个输入的函数：一个表示键值对的元组列表和一个包含要搜索的键的列表。然后该函数应该在整个列表中搜索这些键的所有出现并返回它们。

因为这个关于 Erlang 的第一个练习是为了让我们熟悉该语言的基本概念，这意味着我们应该通过使用递归而不是 list:max 之类的东西来解决这些任务。

我能够为之前的任务实现一个工作函数，该任务只是在键值对元组列表中搜索一个键并返回第一个结果。那个的实现似乎很容易，但是为了扩展这个任务，我尝试了很多不起作用的东西，我什至不知道接下来要尝试什么。

目前我尝试了这种方法：

find_all(Keys, Values) ->
  AllFindings = [],
  lists:foreach(
    fun(Key) ->
      lists:foreach(
        fun(Value) ->
          {X, Y} = Value,
          case X == Key of
            true -> AllFindings:append(Value);
            false -> []
          end
        end,
        Values
      )
    end,
    Keys
  ),
  AllFindings.

这样做的问题是，要么我需要做一些事情，比如将值附加到最初创建的列表中（这给了我这个错误：Warning: invalid module and/or function name; this call will always fail而且我不确定这是否可能以我想要的方式工作，因为它需要变量 AllFindings 来改变它的值）或者我需要一种方法来保存这些值以供以后使用，这样我就可以在以后将所有值放在一起时将它们全部输出。

但我不确定如何正确实现这一目标。

我以前尝试实现的方法是这样的，使用递归，但没有按照我希望它们工作的方式工作（此版本中的一些值输出仅用于“调试”以查看哪个变量具有哪个值函数的状态）：

find_all(Keys = [KeyHead | KeyTail], Values = [ValueHead | ValueTail]) ->
  Tuples = [X || X = {KeyHead, Y} <- [ValueHead]],
  Tuples,
  ValueTail,
  case Tuples /= [] of
    true -> Tuples
  end,
  case ValueTail /= [] of
    true -> find_all(Keys, ValueTail);
    false ->
      case KeyTail /= [] of
        true -> find_all(KeyTail, Values);
        false -> find_all(KeyTail, ValueTail)
      end
  end.

和：

find_all([], []) -> [];
find_all([KeyHead | KeyTail], [ValueHead | ValueTail]) ->
  case ValueHead of
    {KeyHead, V} -> V;
    {_, V} -> find_all(KeyTail, ValueHead);
    _ -> find_all(KeyHead, ValueTail)
  end.

对于解决这个问题的任何建议，我都会非常感激，无论是通过建议一些代码还是将我指向相应的文献，因为对我来说，关于 Erlang 的文献/论坛似乎非常稀少且难以找到（尤其是与流行语言相比时Java 或 Python）。到目前为止，我还在阅读“Learn You Some Erlang”，但没有遇到任何我认为它可能有助于解决这个问题的特定部分。

编辑

我现在想出了这段代码：

find_all(Keys, Values) ->
  while(Keys, Values).

while([], []) -> [];
while(Keys = [KeyHead | KeyTail], Values = [ValueHead | ValueTail]) ->
  NumberOfKeys = length(Keys),
  LengthOfValues = length(Values),
  {K, V} = ValueHead,
  erlang:display(Keys), erlang:display(Values),
  case NumberOfKeys > 1 of
    true -> case LengthOfValues > 1 of
              true -> case K =:= KeyHead of
                        true -> [ValueHead | find_all(Keys, ValueTail)];
                        false -> [find_all(Keys, ValueTail)]
                      end;
              false -> case K =:= KeyHead of
                         true -> [ValueHead];
                         false -> []
                       end
            end;
    false -> case LengthOfValues > 1 of
               true -> case K =:= KeyHead of
                         true -> [ValueHead | find_all(Keys, ValueTail)];
                         false -> [find_all(Keys, ValueTail)]
                       end;
               false -> case K =:= KeyHead of
                          true -> [ValueHead];
                          false -> []
                        end
             end
  end,
  while(KeyTail, Values).

在我看来，它看起来很有希望，因为它的一个较小版本已经为此函数调用返回 {d, 3} warmup:find_all([d, x, c], [{c, 5}, {z, 7}, {d, 3}, {a, 1}]).。当使用erlang:display()不同的值进行调试时，我可以看到它在第一个键上循环了 4 次，并且还减少了ValueTail最后一个值，然后转到下一个键。但是我很困惑为什么 thenValues仍然只包含最后一个 value {a, 1}，因为我认为递归会回到它的调用的顶层，其中列表仍然应该包含所有值？

标签： erlangtupleskeykey-value

解决方案

这个问题很长，所以为了清楚起见，这里是问题陈述：编写一个函数，它接受一个键值对元组列表和一个键列表，并使用递归，返回每个键与任何键匹配的列表给定的键。鉴于这个问题陈述，我们可以编写模块的顶部——我们称之为keyfinder——导出一个find/2函数：

-module(keyfinder).
-export([find/2]).

现在，让我们考虑一些琐碎的情况：

空对列表：返回一个空列表。
空键列表：返回一个空列表。

我们可以使用模式匹配来编写这两种情况：

find([], _) -> []; % no pairs
find(_, []) -> []; % no keys

接下来，让我们考虑剩下的情况，我们有对和键：给定n 个键，我们必须搜索对列表n次，并保留我们找到的每个匹配项的列表。要跟踪匹配，我们可以使用累加器列表，从空开始。也许我们可以find/3为此使用 a ，其中额外的参数是累加器：

find(Pairs, Keys) ->
    find(Pairs, Keys, []).

我们想find/3递归调用自己来查找所有匹配项，所以让我们考虑find/3必须处理的情况：

对列表头的键与键列表头的键匹配：将对添加到累加器并递归搜索其余对以找到相同的键。
对列表头部的键与键列表头部的键不匹配：递归地在其余对中搜索相同的键。
键列表为空：返回累加器。
对列表是空的：我们的递归最终通过遍历对列表到达这里；递归搜索整个对列表中的每个剩余键。

在上面的最后一种情况下，我们的递归可能导致我们检查了所有对，从而清空了我们的对列表，但还有更多的键要搜索；这意味着我们需要将原始配对列表保留在某个地方，以便使用下一个键重新开始搜索。一种方法是添加另一个参数，即对的原始列表：

find(Pairs, Keys) ->
    find(Pairs, Keys, Pairs, []).

这使得我们的递归函数find/4代替了find/3，并且我们将原始的对列表不变地传递给每个find/4调用。

让我们find/4分别处理上述四种情况：

%% We exhausted the list of keys, so return the results.
find(_, [], _, Results) -> Results;

%% We exhausted the list of pairs, so search for the rest of the keys.
find([], [_|Keys], OriginalPairs, Results) ->
    find(OriginalPairs, Keys, OriginalPairs, Results);

%% Our pair matches our key, so add the pair to the accumulator and continue the search.
find([{Key,_}=Pair|Pairs], [Key|_]=Keys, OriginalPairs, Results) ->
    find(Pairs, Keys, OriginalPairs, [Pair|Results]);

%% No match, continue the search.
find([_|Pairs], Keys, OriginalPairs, Results) ->
    find(Pairs, Keys, OriginalPairs, Results).

最有趣的情况是第三个子句，我们在函数头中使用模式匹配来匹配对中的键与键列表头部的键。当匹配发生时，我们的递归调用find/4传递一个新的累加器，该累加器由新找到的对作为新累加器的头部和原始累加器作为它的尾部。该函数子句和最后一个子句都使用对列表的尾部作为递归find/4调用的第一个参数。

完整模块：

-module(keyfinder).
-export([find/2]).

find([], _) -> [];
find(_, []) -> [];
find(Pairs, Keys) ->
    find(Pairs, Keys, Pairs, []).

find(_, [], _, Results) -> Results;
find([], [_|Keys], OriginalPairs, Results) ->
    find(OriginalPairs, Keys, OriginalPairs, Results);
find([{Key,_}=Pair|Pairs], [Key|_]=Keys, OriginalPairs, Results) ->
    find(Pairs, Keys, OriginalPairs, [Pair|Results]);
find([_|Pairs], Keys, OriginalPairs, Results) ->
    find(Pairs, Keys, OriginalPairs, Results).

让我们编译它并在 Erlang shell 中尝试一下：

1> c(keyfinder).
c(keyfinder).
{ok,keyfinder}
2> keyfinder:find([],[]).
keyfinder:find([],[]).
[]
3> keyfinder:find([{a,1}],[]).
keyfinder:find([{a,1}],[]).
[]
4> keyfinder:find([],[a]).
keyfinder:find([],[a]).
[]
5> keyfinder:find([{a,1}],[a]).
keyfinder:find([{a,1}],[a]).
[{a,1}]
6> keyfinder:find([{a,1},{a,2}],[a]).
keyfinder:find([{a,1},{a,2}],[a]).
[{a,2},{a,1}]
7> keyfinder:find([{a,1},{a,2}],[a,b]).
keyfinder:find([{a,1},{a,2}],[a,b]).
[{a,2},{a,1}]
8> keyfinder:find([{a,1},{b,2}],[a,b]).
keyfinder:find([{a,1},{b,2}],[a,b]).
[{b,2},{a,1}]
9> keyfinder:find([{a,1},{b,2},{c,3}],[a,b]).
keyfinder:find([{a,1},{b,2},{c,3}],[a,b]).
[{b,2},{a,1}]
10> keyfinder:find([{a,1},{b,2},{c,3}],[a,b,c,d,e]).
keyfinder:find([{a,1},{b,2},{c,3}],[a,b,c,d,e]).
[{c,3},{b,2},{a,1}]

似乎按预期工作。

请注意，结果列表是从找到的最后一个匹配项到第一个匹配项排序的，这是因为我们将每个结果都添加到累加器列表中。如果您更喜欢相反的顺序，并且如果您被允许使用该lists模块，则可以更改第一个子句find/4以在返回结果之前反转结果：

find(_, [], _, Results) -> lists:reverse(Results);

如果您不允许使用该lists模块，那么您可以通过将每一对附加到累加器列表来避免反转结果的需要：

find([{Key,_}=Pair|Pairs], [Key|_]=Keys, OriginalPairs, Results) ->
    find(Pairs, Keys, OriginalPairs, Results++[Pair]);

请注意，这比预先添加的效率要低一些。

erlang - 查找元组列表中的所有元组

问题描述

解决方案

推荐阅读