Анализ рекурсивного списка в Erlang

Question

Я играю с Erlang и пытаюсь написать парсер S-expression. Я считаю, что это простая задача в Python с использованием стеков и циклов, но для меня это нетривиально как новичок в неизменяемых переменных и структурах данных Erlang.

Мне нужно, чтобы преобразовать список в Erlang, как это:

X = ["0", "(", "1", "2", "3", ")"], 
Res = transform(X). % ["0", ["1", "2", "3"]] 

К настоящему времени, я пришел к этому:

transform(List) -> 
    lists:map(fun(X)-> 
         case string:equal("(", X) of 
          %% recursive call with sublist of List from "(" to ")" as argument 
          true -> transform_to_list(Lack) 
         end 
       end, List). 

Не знаете, как получить подсписок Lack и передать его как аргумент. Я иду в правильном направлении?

Answer 1

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

-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"] 

Answer 2

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

Списки: функция отображения не может использоваться в случае этого анализа, поскольку она применяет только данную функцию к каждому элементу списка для создания нового списка, который будет иметь одинаковую длину. Невозможно создать вложенный список. Как говорит @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], это хорошая привычка, потому что он избегает, чтобы сделать совершенно новый список на каждом (и сделаю это, я избегу замечания от моего друга @ Хайнека-Пичи-Выходила: o). Поэтому я должен отменить список, когда захочу его сохранить.

Используя 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"]