2

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

最初の質問は、erlang での循環リストの正確な意味は何ですか? リストに格納されている2つの要素がありますか?

もしそうなら、erlang で循環リストを定義する可能性があると言えます。しかし、明確にする必要があります天気は、循環リストがアーランにあると思いますか?

4

5 に答える 5

8

それを行う組み込みのリストメカニズムはありません。ただし、アクセスしたかどうかに関係なく、要素を保持するタプルを使用して構築できます。

基本的な構造は、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}.

これにより、関数「next」、「peek」、および場合によっては「delete」(下記参照) を使用して通常の操作を行うことができます。逆方向のブラウジングを可能にする「prev」関数を追加することもできます。

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};

そして、それはそれのほとんどをカバーするはずです.

于 2012-01-27T21:42:55.717 に答える
5

erlang と erlang 仮想マシンを見ると、不変データのみがサポートされているため、循環リストを作成することはできません。何らかの「違法な」方法で自分で作成した場合、メモリ管理がそれを適切に処理できるかどうかは定かではありません。

于 2012-01-16T22:22:34.647 に答える
4

仮想マシンでサポートされているErlangには循環リストはありません。必要に応じて、自分で作成する必要があります。

于 2012-01-16T19:30:55.690 に答える
3

はい、できます ;)

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.
于 2012-01-19T15:37:04.263 に答える
1

上で指摘したように、それらを自分で実装する必要があります。しかし、erlang ではさまざまな方法でデータを他のデータに関連付けることができるため、そうすることを妨げるものは何もありません。基本的に、現在のインデックスを表すものと、次のインデックスへのポインターを表すものだけが必要です。面白い方法の 1 つは、PID によって次の (または前の) プロセス (要素) を指すリスト内の各要素のプロセスを開始することです。1 つ (または多数) の特別な目的のプロセスが、他の「リスト」プロセスをクロールしている可能性があります。クレイジーでないアプローチでは、ets や mnesia を利用するかもしれません。

于 2012-01-16T23:12:52.080 に答える