2

是否可以在 erlang 中定义一个循环列表？ http://en.wikipedia.org/wiki/Linked_list

第一个问题是 erlang 中的循环列表到底意味着什么？它是否有两个元素，一个元素是它自己，它旁边是下一个元素的地址，存储在一个列表中？

如果是这样，我可以说有可能在 erlang 中定义一个循环列表。但我需要澄清一下天气是我认为erlang中的循环列表吗？

4

5 回答 5

8

没有内置的列表机制可以做到这一点。但是，您可以使用包含您访问过或未访问过的元素的元组来构建一个。

基本结构是一个包含两个列表的元组：{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}}.

如果列表中没有任何内容，则会崩溃。如果你想通过特殊的大小写它，你也可以返回 'undefined'：

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

这应该涵盖了大部分内容。

于 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 中以各种方式将数据与其他数据相关联，因此没有什么能阻止您这样做。本质上，您只需要一个代表当前索引的东西和另一个代表指向下一个索引的指针。一种有趣的方法是为列表中的每个元素启动一个进程，通过其 PID 指向下一个（或上一个）进程（元素）。一个（或多个）特殊用途进程可能正在爬取那些其他“列表”进程。不那么疯狂的方法可能会使用 ets 或 mnesia。

于 2012-01-16T23:12:52.080 回答