Erlangの再帰的リスト解析

Question

私はErlangと一緒に遊んでいて、S式パーサを書こうとしています。私はそれがスタックとループを使ってPythonで簡単な作業であることがわかりますが、不変の変数とErlangのデータ構造の初心者として私にとっては自明ではありません。

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

が今では、私はこれに来ている：

は、私はこのようなErlangでリストを変換する必要が

サブリスト Lackを取得し、それを渡す方法

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). 

わかりません議論として。 正しい方向に進んでいますか？

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番目の句は、新しいサブリストを開始する"("を認識します。これを処理するために、アキュムレータを2タプルに変更します。最初の項目はサブリストアキュムレータで、2番目の項目は古いアキュムレータです。

• 3番目と4番目の句はサブリストを終了する")"を処理します。 3番目の節は、アキュムレータがタプルでもある2番目の要素を保持するタプルの場合です。新しいサブリストを項目として前のサブリストに追加し、アキュムレータタプルから1つのレベルをポップします。第4節は、タプル内の元の累算器がリストである場合を処理し、元の累算器の先頭に新しいサブリストを追加して新しい累算器リストを形成する。

• 5番目と6番目の句は、グループ化演算子ではない入力項目を処理します。 5番目の句は、アキュムレータがタプルの場合のケースを処理し、6番目の句はアキュムレータがリストの場合のケースを処理します。あなたの元の例でこれを実行する

が正しい答えを示しています。

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

私はあなたが既に答えを得たけど、私ビーチに行く前にあなたの質問を読んでください。私はカイトサーフ "バレエ"を見ている間にこの1つを想像しました。私はそれを与えるので、それはスティーブワンとは少し違っています。

この分析の場合は、リストの各要素に所定の関数を適用して同じ長さの新しいリストを作成するため、map関数はこの分析の場合には使用できません。ネストされたリストを作成する方法はありません。 @Steveによれば、結果を徐々に構築するにはアキュムレータが必要です。

リストライブラリは、リストをたどる間に用語を累積する関数を提供します：リスト：foldl/3（foldr、mapfoldl、およびmapfoldrも存在します）。この場合の問題は、ビルドするのに役立つアキュムレータを定義することです期待される結果。

• 最も単純なリストには括弧がないため、アキュムレータにはエントリリストのすべての要素を累積するリストが含まれている必要があります。

• しかし、「（」が出現した場合、結果にネストしなければならないサブリストを含む新しいリストを開始する必要があります。この場合、リストを含む用語が必要です。単一のフォームで2人のニーズに適合することができます構築するためのサブリスト、そして我々は「（」が発生した時に進行中であったリスト

最も簡単な構造は、リストのリストです：[SublistInProgress|PreviousWork]

今私たちはアキュムレータの形式を知っており、3つのケースを担当する関数を定義することができます：

• 我々は見つける「（」：我々はAを見つける
• 前のアキュムレータ新しいサブリストを起動し、そして「ストア」「）」：
• 前のアキュムレータにサブリストを追加し、他の場合には、追加要素を進行中のサブリストに追加します。シェルで

：

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> 

注：私はむしろHacC++ [X]よりも構造[X|Hacc]を使用して、リスト内の要素を蓄積し、それはそれぞれで全く新しいリストを作るために回避するので、それは良い習慣ですステップ（これを行うと、私は友人@ Hynek-Pichi-Vychodilからの発言を避ける：o）。だから私はそれを保存したいときにリストを逆にしなければならない。

ファンクションlists:foldl(F,[[]],L)でFを使用すると、1つの要素のリストが得られます。この要素は、期待される結果の逆です。

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