Вопрос длинный, поэтому для ясности, вот формулировка проблемы: напишите функцию, которая принимает список пар пары ключ-значение и список ключей и, используя рекурсию, возвращает список каждой пары, чей ключ соответствует любой из указанных ключей. Учитывая это постановку задачи, мы можем написать верхнюю часть нашего модуля - назовем его keyfinder - для экспорта функции find/2:
-module(keyfinder).
-export([find/2]).
Теперь давайте рассмотрим тривиальные случаи:
- Пустой список пар: возвращает пустой список.
- Пустой список ключей: возвращает пустой список.
Мы можем записать эти два случая, используя сопоставление с образцом:
find([], _) -> []; % no pairs
find(_, []) -> []; % no keys
Далее, давайте рассмотрим оставшийся случай, когда у нас есть пары и ключи: учитывая n ключей, мы должны искать список пар n раз и список всех найденных совпадений. Для отслеживания матчей мы можем использовать список аккумуляторов, начиная с пустого. Возможно, мы можем использовать find/3 для этого, где дополнительным аргументом является аккумулятор:
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:
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]);
Обратите внимание, что это немного менее эффективно, чем предваряющий, хотя.