Может ли Циркулярные списки задаваться в Эрланге?

Question

Можно ли определить круговой список в erlang? http://en.wikipedia.org/wiki/Linked_list

Первый вопрос будет таким, какой именно круглый список означает в erlang? это два элемента, один элемент - сам, а рядом с ним - адрес следующего элемента, сохраненный в списке?

Если так, я могу сказать, что есть возможность определить круговой список в erlang. , но мне нужна погода осветления, это то, что я считаю круговым списком в erlang?

Answer 1

Там нет встроенных в список механизм, чтобы сделать это. Тем не менее, вы можете построить один, используя кортеж, содержащий элементы, которые вы посещали, или нет.

Основная структура - это кортеж с двумя списками: {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}. 

Это то позволяет использовать функцию «рядом», «заглядывать» и, возможно, «удалить» (см ниже), чтобы сделать нормальные вещи ,Мы могли бы также добавить функцию «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}; 

И это должно охватывать большую часть его.

Answer 2

В Эрланге нет циркулярных списков, поддерживаемых виртуальной машиной. Вы должны построить их самостоятельно, если хотите.

Answer 3

Видя erlang и виртуальную машину erlang, поддерживает только неизменяемые данные, невозможно создать круговой список. Если вы должны были создать один из них каким-то «незаконным» способом, то не уверен, что управление памятью может справиться с ним должным образом.

Answer 4

Как указано выше, вы должны были бы реализовать их самостоятельно. Но поскольку вы можете связать данные с другими данными различными способами в erlang, вам ничего не мешает. По существу вам требуется всего одна штука, представляющая текущий индекс, а другая - указатель на следующий индекс. Один забавный способ - начать процесс для каждого элемента в списке, указывающего на следующий (или предыдущий) процесс (элемент) его PID. Один (или много) процесс (ы) специального назначения может сканировать те другие «списки» -процессов. Менее сумасшедшие аплоасы могут использовать ets или mnesia.

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.