можно ли определить круговой список в erlang? http://en.wikipedia.org/wiki/Linked_list
Первый вопрос будет заключаться в том, что именно круговой список означает в erlang? это с двумя элементами, один элемент сам по себе, а рядом с ним адрес к следующему элементу, хранящемуся в списке?
если это так, я могу сказать, что есть возможность определить круговой список в erlang. но мне нужно уточнение погоды, это то, что я думаю, что круговой список в erlang?
Для этого нет встроенного механизма списка. Однако вы можете создать его, используя кортеж, содержащий элементы, которые вы посетили или нет.
Базовая структура представляет собой кортеж с двумя списками: {Old, New}. Когда вы впервые начинаете с пустого списка, он выглядит как {[],[]}. Когда вы заполняете список, вы заполняете его в списке New:
new() -> {[], []}.
insert(X, {Old, New}) -> {Old, [X|New]}.
peek({_Old, [H|_]}) -> X.
Чтобы перемещаться по списку, вы сначала ищете в списке New и помещаете значение в старый:
next({Old, [H|New]}) -> {[H|Old], New}.
Это нормально, и это работает так, как если бы мы просто отбрасывали старые элементы. Что происходит, когда мы доходим до конца списка? Нам нужно исправить функцию (а также peek):
peek({Old, []}) -> hd(lists:reverse(Old));
peek({_Old, [H|_]}) -> X.
next({Old, []}) ->
{[], lists:reverse(Old)}}.
next({Old, [H|New]}) ->
{[H|Old], New}}.
Если в списке ничего нет, происходит сбой. Вы также можете вернуть 'undefined', если хотите, в специальном корпусе:
next({[], []}) ->
undefined;
next({Old, []}) ->
{[], lists:reverse(Old)}.
next({Old, [H|New]}) ->
{[H|Old], New}.
Затем это позволяет вам использовать функции «далее», «заглянуть» и, возможно, «удалить» (см. Ниже), чтобы делать обычные вещи. Мы также можем добавить функцию «предыдущая», чтобы разрешить просмотр назад:
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};
И это должно охватывать большую часть этого.
Видя, что erlang и виртуальная машина erlang поддерживают только неизменяемые данные, невозможно создать циклический список. Если бы вы сами построили его каким-то «незаконным» способом, то нет уверенности, что управление памятью сможет справиться с этим должным образом.
В Erlang нет циклических списков, поддерживаемых виртуальной машиной. Вы должны построить их сами, если хотите.
Почему да, можно ;)
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.
Как указывалось выше, вам придется реализовать их самостоятельно. Но поскольку в erlang вы можете связать данные с другими данными различными способами, ничто не мешает вам это сделать. По сути, вам нужна только одна штука, представляющая текущий индекс, и другая, представляющая указатель на следующий индекс. Одним из забавных способов было бы запустить процесс для каждого элемента в списке, указывающего на следующий (или предыдущий) процесс (элемент) по его PID. Один (или несколько) процессов специального назначения может сканировать эти другие процессы «списка». Менее сумасшедшие подходы могут использовать ets или мнезию.
