Erlang 中可以定义循环列表吗？

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 函数）：

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({[], []}) ->
    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和erlang虚拟机只支持不可变数据，不可能构建循环列表。如果您要以某种“非法”方式自己构建一个，那么不确定内存管理是否可以正确处理它。

Answer 3

Erlang 中没有虚拟机支持的循环列表。如果你想要的话，你必须自己建造它们。

Answer 4

为什么是的，你可以；）

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.

Answer 5

如上所述，您必须自己实施它们。但是，由于您可以在 erlang 中以各种方式将数据与其他数据关联起来，因此没有什么可以阻止您这样做。
本质上，您只需要一个代表当前索引的东西和另一个代表指向下一个索引的指针。一种有趣的方法是为列表中的每个元素启动一个进程，通过其 PID 指向下一个（或上一个）进程（元素）。一个（或多个）特殊用途进程可能正在抓取那些其他“列表”进程。不太疯狂的方法可能会使用 ets 或 mnesia。