在元组列表中查找所有元组

Question

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

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

由于关于 Erlang 的第一个练习旨在让我们熟悉该语言的基本概念，这意味着我们应该使用递归而不是 lists:max 之类的方法来解决这些任务。

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

目前我尝试过这种方法：

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 来更改它的值）或者我需要一种方法来保存这些值以备后用，这样我就可以在以后的某个时间点将它们一起输出所有值一起。

但我不太确定如何正确地实现它。

我以前尝试实现这个的方法是这样的，使用递归但没有按照我预期的方式工作（这个版本中的一些值输出仅用于 "debugging" 到查看什么变量在函数的什么状态下具有什么值）：

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.

我真的很感激任何关于解决这个问题的建议，无论是通过建议一些代码还是通过将我指向相应的文献，因为对我来说 literature/forums 在 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).

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

Answer 1

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

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

现在，让我们考虑一些简单的情况：

空列表对： return 一个空列表。
键的空列表： return 一个空列表。

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

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

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

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

我们希望 find/3 递归调用自身以找到所有匹配项，因此让我们考虑一下 find/3 必须处理的情况：

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

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

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 的第一个子句以在 returning 之前反转结果：

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

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

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

请注意，这比前置要低一些。

Answer 2

您可以尝试使用列表生成器在列表中查找元组。

在简单列表中查找 key/value 的元组：

1> [X || {_, _} = X <- [{a, 1}, 1, [2], {b, 2}, {c, 3}, 4]].
[{a,1},{b,2},{c,3}]

在嵌套列表中查找元组：

1> Data = [[d, x, c], [{c, 5}, {z, 7}, {d, 3}, {a, 1}, 1, [1, 2, {x, 1}, {j, 1}]]].
[[d,x,c],[{c,5},{z,7},{d,3},{a,1},1,[1,2,{x,1},{j,1}]]]
2> [X || {_, _} = X <- lists:flatten(Data)].
[{c,5},{z,7},{d,3},{a,1},{x,1},{j,1}]

在不限制嵌套列表中元组元素数量的情况下查找元组：

1> Data = [[d, x, c], [{c, 5, 5}, {z, 7}, {d, 3, 3}, {a, 1}, 1, [1, 2, {x, 1, 1}, {j, 1}]]].
[[d,x,c],
 [{c,5,5},{z,7},{d,3,3},{a,1},1,[1,2,{x,1,1},{j,1}]]]
2> [X || X <- lists:flatten(Data), is_tuple(X)].
[{c,5,5},{z,7},{d,3,3},{a,1},{x,1,1},{j,1}]

在元组列表中查找所有元组

Find all tuples within a list of tuples

erlang

tuples

key

key-value