Erlang中的递归列表分析

Question

我正在学习Erlang并尝试编写S表达式解析器。在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并将其作为参数传递。 我的方向正确吗？

- asyndrige

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函数中完成。 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"]

- Steve Vinoski

---

感谢您的完美解释！ - asyndrige

Answer 2

我知道你已经得到了一个答案，但是昨天在去海滩之前我看到了你的问题，当我看着风筝冲浪“芭蕾舞”时，我想到了这个答案，所以我提供给你，它与 Steve 的答案有点不同，可能会更有趣。

在这种情况下，无法使用 lists:map 函数进行分析，因为它仅将给定函数应用于列表的每个元素以构建具有相同长度的新列表。无法构建嵌套列表。正如 @Steve 所说，您需要一个累加器来逐步构建结果。

lists 库提供了一种在遍历列表时累积项的函数：lists:foldl/3（也存在 foldr、mapfoldl 和 mapfoldr），在这种情况下，问题在于定义将帮助我们构建预期结果的累加器。

• 最简单的要分析的列表没有括号，因此累加器应该包含一个列表，其中累积输入列表的所有元素。

• 但是，如果我们遇到“（”，我们应该开始一个新列表，其中包含我们必须嵌套在结果中的子列表。在这种情况下，我们需要一个包含列表的术语，我们可以将新子列表放入其中以构建，并且当我们遇到“（”时正在进行的列表。

可以适合单个形式中的2个需求的最简单结构是列表的列表：[SublistInProgress|PreviousWork]

现在我们知道了累加器的形式，我们可以定义负责构建它的函数，有3种情况：

• 我们找到了“（”：开始一个新的子列表，并“存储”先前的累加器
• 我们找到了“）”：将子列表添加到先前的累加器中
• 任何其他情况都将元素添加到正在进行的子列表中。

在 shell 中：

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-Vychodil的评论:o）。因此，当我要存储它时，必须将列表反转。

在函数lists:foldl(F,[[]],L)中使用F，我们将得到一个元素的列表，该元素是期望结果的反向。因此，我们必须将此调用嵌入特定的函数库中：

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

- Pascal

---

好的，这是一个优雅而简洁的解决方案。我会记下来的。谢谢！ - asyndrige