Рекурсивный анализ списка в Erlang

Вы можете решить это, используя аккумулятор и сопоставление с образцом:

-module(t).
-export([transform/1]).

transform(List) ->
    transform(List, []).

transform([], Acc) ->
    lists:reverse(Acc);
transform(["("|T], Acc) ->
    transform(T, {[],Acc});
transform([")"|T], {L,{L2,Acc}}) ->
    transform(T, {[lists:reverse(L)|L2],Acc});
transform([")"|T], {L,Acc}) ->
    transform(T, [lists:reverse(L)|Acc]);
transform([H|T], {L,Acc}) ->
    transform(T, {[H|L],Acc});
transform([H|T], Acc) ->
    transform(T, [H|Acc]).

Функция transform/1 просто устанавливает пустой аккумулятор для transform/2, где и выполняется вся работа.

Функция transform/2 разделена на несколько рекурсивных предложений, соответствующих шаблону:

• Первое предложение обрабатывает случай, когда мы исчерпали входной список, и просто возвращает обратный аккумулятор. Обращение необходимо, потому что элементы помещаются в аккумулятор, поэтому он оказывается в обратном порядке. Это распространенный шаблон в Erlang и других функциональных языках.

• Второе предложение распознает "(", с которого начинается новый подсписок. Чтобы справиться с этим, он изменяет аккумулятор на 2-кортеж, где первый элемент является аккумулятором подсписка, а второй элемент — старым аккумулятором.

• Третье и четвертое предложения обрабатывают ")", которым заканчивается подсписок. Третье предложение предназначено для случая, когда аккумулятор представляет собой кортеж, содержащий второй элемент, который также является кортежем; он добавляет новый подсписок в качестве элемента к предыдущему подсписку и извлекает один уровень из кортежа накопителя. Четвертое предложение обрабатывает случай, когда исходный аккумулятор в кортеже представляет собой список, добавляя новый подсписок к заголовку исходного аккумулятора для формирования нового списка аккумуляторов.

• Пятое и шестое предложения обрабатывают элементы ввода, которые не являются операторами группировки. Пятое предложение обрабатывает случай, когда аккумулятор представляет собой кортеж, а шестое предложение обрабатывает случай, когда аккумулятор представляет собой список.

Выполнение этого на исходном примере показывает правильный ответ:

1> c(t).
{ok,t}
2> t:transform(["0", "(", "1", "2", "3", ")"]).
["0",["1","2","3"]]

Но он также может обрабатывать вложенные группы:

3> t:transform(["0", "(", "11", "22", "(", "333", "444",
                "(", "5555", ")", "666", ")", "77", "88", ")", "9"]).
["0",["11","22",["333","444",["5555"],"666"],"77","88"],"9"]

Я знаю, что у вас уже есть ответ, но я прочитал ваш вопрос вчера перед тем, как пойти на пляж, и я представил этот вопрос, когда смотрел на «балет» кайтсерфинга, поэтому я даю его, он немного отличается от Стива. , так что может быть интересно.

Функцию lists:map нельзя использовать в случае этого анализа, потому что она применяет заданную функцию только к каждому элементу списка для построения нового списка той же длины. Нет возможности построить вложенный список. Как говорит @Steve, вам нужен аккумулятор для постепенного построения результатов.

Библиотека списков предлагает функцию для накопления терминов при обходе списка: lists:foldl/3 (есть также foldr, mapfoldl и mapfoldr), проблема в данном случае состоит в том, чтобы определить аккумулятор, который поможет нам построить ожидаемый результат.

• Самый простой список для анализа не имеет круглых скобок, поэтому аккумулятор должен содержать список, в котором будут накапливаться все элементы списка записей.

• Но если мы встретим «(», мы должны начать новый список, который будет содержать подсписок, который мы должны вложить в результат. В этом случае нам нужен терм, содержащий список, в котором мы можем поместить новый подсписок для построения, и список, который был в процессе, когда мы сталкиваемся с "(".

самая простая структура, которая может удовлетворить 2 потребности в одной форме, — это список из списка: [SublistInProgress|PreviousWork]

Теперь мы знаем форму нашего аккумулятора, мы можем определить функцию, отвечающую за его создание, 3 случая:

• мы находим "(": начинаем новый подсписок и "сохраняем" предыдущий аккумулятор
• находим ")": добавляем подсписок к предыдущему аккумулятору
• в любом другом случае добавьте элемент в подсписок.

в оболочке:

1>  F = fun("(",Acc)-> [[],Acc];                                               
1>         (")",[SubList,[Hacc|Tacc]]) -> [[lists:reverse(SubList)|Hacc]|Tacc];
1>         (X,[Hacc|Tacc]) -> [[X|Hacc]|Tacc] end.                             
#Fun<erl_eval.12.52032458>

Примечание: я накапливаю элемент в списке, используя конструкцию [X|Hacc], а не Hacc ++ [X], это хорошая привычка, потому что она позволяет избежать создания совершенно нового списка на каждом шаге (и при этом я избегу замечания от моего друга @Hynek-Pichi -Выходил :о). Поэтому мне нужно перевернуть список, когда я хочу его сохранить.

Используя F в функции lists:foldl(F,[[]],L) мы получим список из одного элемента, этот элемент является обратным ожидаемому результату. Итак, мы должны встроить этот вызов библиотеки в конкретную функцию:

2> Transform = fun(L) -> [R] = lists:foldl(F,[[]],L),
2>                       lists:reverse(R) end.
#Fun<erl_eval.6.52032458>

и мы можем проверить это:

3> L1 = ["0", "(", "1", "2", "3", ")"].
["0","(","1","2","3",")"]
4> L2 = ["0", "(", "11", "22", "(", "333", "444","(", "5555", ")", "666", ")", "77", "88", ")", "9"].
["0","(","11","22","(","333","444","(","5555",")","666",")",
 "77","88",")","9"]
5> Transform(L1).
["0",["1","2","3"]]
6> Transform(L2).
["0",["11","22",["333","444",["5555"],"666"],"77","88"],"9"]