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 并将其作为参数传递。我的方向对吗？

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函数被分成多个模式匹配递归子句：

第一个子句处理我们已经用尽输入列表的情况，它只是 returns 反向累加器。需要反转，因为项目被推入累加器，所以它以相反的顺序结束。这是 Erlang 和其他函数式语言中的常见模式。
第二个子句识别 "("，它开始一个新的子列表。为了处理它，它将累加器更改为二元组，其中第一项是子列表累加器，第二项是旧累加器。
第三个和第四个子句处理 ")"，它结束了一个子列表。第三个子句适用于累加器是一个包含第二个元素的元组的情况，该第二个元素也是一个元组；它将新的子列表作为一个项目添加到先前的子列表中，并从累加器元组中弹出一个级别。第四个子句处理元组中原累加器是列表的情况，将新的子列表添加到原累加器的头部，形成新的累加器列表。
第五个和第六个子句处理不是分组运算符的输入项。第五个子句处理累加器是元组的情况，而第六个子句处理累加器是列表的情况。

运行你原来的例子显示了正确答案：

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

我知道你已经得到了答案，但我昨天去海滩之前看了你的问题，我在看风筝冲浪时想象了这个 "ballet"，所以我给它，它是与史蒂夫的有点不同，所以它可能很有趣。

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

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

要分析的最简单的列表没有括号，所以累加器应该包含一个列表，在该列表中累加条目列表的所有元素。
但是如果遇到“(”，我们应该开始一个新的列表，其中包含我们必须嵌套在结果中的子列表。在这种情况下，我们需要一个包含列表的术语我们可以把新的子列表放到构建中，遇到"(".

能以单一形式满足2种需求的最简单的结构是list of list：[SublistInProgress|PreviousWork]

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

我们找到一个“(”：开始一个新的子列表，并且"store"之前的累加器
我们找到一个“)”：将子列表添加到前一个累加器
任何其他情况将元素添加到正在进行的子列表中。

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

Erlang 中的递归列表分析

Recursive list analysis in Erlang

erlang

s-expression