Erlangで循環リストを定義できますか？

Question

erlangで循環リストを定義することは可能ですか？ http://en.wikipedia.org/wiki/Linked_list

最初の質問は、正確に円形リストがerlangで意味するものでしょうか？ それは2つの要素、1つの要素の自己であり、次の要素にアドレスして、リストに格納されていますか？

もしそうなら、私はerlangで循環リストを定義する可能性があると言うことができます。 しかし、私は明確な天気が必要ですそれは私が円形リストがerlangにあると思いますか？

Answer 1

を証明するために、いくつかの安っぽいコードです。ただし、訪問した要素を保持するタプルを使用して構築できます。

基本構造は、2つのリストを持つタプルです。{Old, New}です。最初に空のリストから始めると、{[],[]}のようになります。リストを記入すると、あなたはNewリストでそれを埋める：

new() -> {[], []}. 

insert(X, {Old, New}) -> {Old, [X|New]}. 

peek({_Old, [H|_]}) -> X. 

リスト内を移動するには、何をやっていることはまずNewリストに追求し、古いものに価値を置いている：

next({Old, [H|New]}) -> {[H|Old], New}. 

これは問題なく、古い要素を破棄したように機能します。しかし、私たちがリストの最後を叩くとどうなりますか？関数を修正する必要があります：

peek({Old, []}) -> hd(lists:reverse(Old)); 
peek({_Old, [H|_]}) -> X. 

next({Old, []}) -> 
    {[], lists:reverse(Old)}}. 
next({Old, [H|New]}) -> 
    {[H|Old], New}}. 

リストに何もない場合、クラッシュします。あなたは特別なケースにそれをすることによってしたい場合にも、「未定義」返すことができます：

next({[], []}) -> 
    undefined; 
next({Old, []}) -> 
    {[], lists:reverse(Old)}. 
next({Old, [H|New]}) -> 
    {[H|Old], New}. 

この後、あなたは、通常のものを行うために関数「次」、「PEEK」と、おそらく「削除」（下記参照）を使用することができます。

prev({[], []}) -> 
    undefined; 
prev({[], New}) -> 
    {lists:reverse(New), Old}. 
prev({[H|Old], New}) -> 
    {Old, [H|New]}. 

delete({Old, []}) -> {[], tl(lists:reverse(Old))}; 
delete({Old,[H|New]}) -> {Old, New}; 

また、ほとんどのものをカバーする必要があります。

Answer 2

仮想マシンでサポートされているErlangには循環リストはありません。あなたがそれを望むなら、あなたは自分でそれを構築しなければなりません。

Answer 3

erlangとerlang仮想マシンを参照すると、不変のデータしかサポートされず、循環リストを構築することはできません。あなたが何らかの "違法な"方法で自分自身を構築するなら、メモリ管理がそれを適切に処理できるかどうかは確かではありません。

Answer 4

上記のように、自分で実装する必要があります。しかし、データをさまざまな方法で他のデータに関連付けることができるので、そうすることからあなたを止めるものは何もありません。 本質的に、現在のインデックスを表す1つのthingieと、次のインデックスへのポインタを表す1つのthingieだけが必要です。 1つの面白い方法は、そのPIDによって次の（または前の）プロセス（要素）を指すリスト内の各要素のプロセスを開始することです。 1つ（または複数）の特殊目的プロセスが他の「リスト」プロセスをクロールする可能性があります。あまり狂っている人は、etsや俗人を使うかもしれません。

Answer 5

なぜそうすることができます;）

14> X = ll:new().   
20496 
15> ll:push(X, 1).   
1 
16> ll:push(X, 2).   
2 
17> ll:push(X, 3).   
3 
18> ll:pop(X).    
3 
19> ll:hd(X). 
2 
20> {V0,R0} = ll:first(X). 
{2,#Ref<0.0.0.80>} 
21> {V1,R1} = ll:next(X, R0). 
{1,#Ref<0.0.0.76>} 
22> {V2,R2} = ll:next(X, R1). 
{2,#Ref<0.0.0.80>} 

そして、ここではそれを行うには組み込みのリストメカニズムはありませんそれを

-module(ll). 
-export([new/0, delete/1, push/2, pop/1, first/1, hd/1, next/2]). 

-define (META_KEY, '$meta_list'). 

-record(elt, {id, val, next}). 
-record(meta, {id =?META_KEY, size, hd, tl}). 

% Returns TID of ETS table representing linked list 
new() -> 
    Tid = ets:new(alist,[{keypos, 2}]), 
    ets:insert(Tid, #meta{size=0, hd=undefined, tl=undefined}), 
    Tid. 

% Delete list/ETS table representing linked list 
delete(AList) -> 
    ets:delete(AList). 

% Returns the value of what was pushed 
push(AList, AnElt) -> 
    #meta{size = Size} = Meta = get_meta(AList), 
    Hd = get_head(AList, Meta), 

    Ref = make_ref(), 
    NewElt = #elt{id=Ref, val=AnElt, next=iif(Size, 0, Ref, Hd#elt.id)}, 
    ets:insert(AList, NewElt), 

    case Size of 
     0 -> ets:insert(AList, Meta#meta{size=1,hd=Ref,tl=Ref}); 
     N -> 
      Tl = get_tail(AList, Meta), 
      ets:insert(AList, Tl#elt{next = Ref}), 
      ets:insert(AList, Meta#meta{size=N+1,hd=Ref}) 
     end, 
    AnElt. 

% Returns the value of the popped element 
pop(AList) -> 
    #meta{size = Size} = Meta = get_meta(AList), 
    Hd = get_head(AList, Meta), 
    case Size of 
    0 -> ok; 
    1 -> 
     ets:insert(AList, Meta#meta{size=0, hd=undefined,tl=undefined}); 
    N -> 
     Next = get_next(AList, Hd), 
     Tail = get_tail(AList, Meta), 
     ets:insert(AList, Meta#meta{size=N-1, hd=Next#elt.id}), 
     ets:insert(AList, Tail#elt{next=Next#elt.id}) 
    end, 
    ets:delete(AList, Hd#elt.id), 
    Hd#elt.val. 

% Returns the value of the first element 
hd(AList)-> 
    {First, _Next} =first(AList), 
    First. 

% Returns {val, ptr_to_tail}. The prt_to_tail can be used in next/2 
first(AList)-> 
    #meta{size = Size} = Meta = get_meta(AList), 
    if 
    Size == 0 -> {undefined, undefined}; 
    true -> 
     Hd = get_head(AList, Meta), 
     {Hd#elt.val, Hd#elt.id} 
    end. 

% Given ptr_to_tal, returns {hd(tail), ptr_to_tail}. 
next(_AList, undefined) ->  
    {undefined, undefined}; 
next(AList, Id) ->  
    case ets:lookup(AList, Id) of 
    [] -> {error, node_missing}; 
    [#elt{next=Next}] -> 
     case ets:lookup(AList, Next) of 
     []-> {error, node_missing}; 
     [#elt{val=Value}] -> 
      {Value, Next} 
     end 
    end. 



%helper functions 
get_meta(List)-> 
    case ets:lookup(List, ?META_KEY) of 
    []   -> {error, corruptlist}; 
    [Meta] -> Meta 
    end. 

get_head(AList, #meta{size = Size, hd=Hd}) -> 
    case Size of 
    0 -> #elt{}; 
    _N -> 
     case ets:lookup(AList, Hd) of 
     []  -> {error, corruptlist}; 
     [Head] -> Head 
     end 
    end. 

get_tail(AList, #meta{size = Size, tl=Tl}) -> 
    case Size of 
    0 -> #elt{}; 
    _N -> 
     [Tail] = ets:lookup(AList, Tl), 
     Tail 
    end. 

get_next(_AList, #elt{next=undefined}) -> #elt{}; 
get_next(AList, #elt{next=Next}) -> 
    case ets:lookup(AList, Next) of 
    [] -> {error, corruptlist}; 
    [Elt] -> Elt 
    end. 


iif(A, B, TruePart, ElsePart)-> 
case A == B of 
    true -> TruePart; 
    false -> ElsePart 
end.