Can Circular Lists be defined in Erlang?

Question

is it possible to define a circular list in erlang? http://en.wikipedia.org/wiki/Linked_list

first question would be what exactly a circular list mean in erlang? is it with two elements, one element its self and next to it address to the next element, stored in a list?

if so i can say there is a possibility of defining a circular list in erlang. but i need clarification weather is it what i think a circular list is in erlang?

Answer 1

There is no built-in list mechanism to do it. However, you can build one using a tuple holding the elements you've visited or not.

The basic structure is a tuple with two lists: {Old, New}. When you first start with an empty list, it looks like {[],[]}. When you fill the list, you fill it in the New list:

new() -> {[], []}.

insert(X, {Old, New}) -> {Old, [X|New]}.

peek({_Old, [H|_]}) -> X.

To move within the list, what you do is first seek in the New list, and put the value in the old one:

next({Old, [H|New]}) -> {[H|Old], New}.

That's fine and it works as if we were just discarding old elements. What happens when we hit the end of the list though? We need to fix the function (and also the peek one):

peek({Old, []}) -> hd(lists:reverse(Old));
peek({_Old, [H|_]}) -> X.

next({Old, []}) -> 
    {[], lists:reverse(Old)}}.
next({Old, [H|New]}) -> 
    {[H|Old], New}}.

If there's nothing in the list, it crashes. You could also return 'undefined' if you wanted to by special casing it:

next({[], []}) ->
    undefined;
next({Old, []}) -> 
    {[], lists:reverse(Old)}.
next({Old, [H|New]}) -> 
    {[H|Old], New}.

This then lets you use the function 'next', 'peek' and possibly 'delete' (see below) to do normal stuff. We could also add a 'prev' function to allow backwards browsing:

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

And that should cover most of it.

Answer 2

There are no circular lists in Erlang supported by the virtual machine. You have to build them yourself if you want one.

Answer 3

As pointed out above, you would have to implement them yourself. But as you can associate data to other data in various ways in erlang there is nothing stopping you from doing so. Essentially you need just one thingie representing the current index and another one representing the pointer to the next index. One funny way would be starting a process for each element in the list pointing to the next(or previous) process(element) by its PID. One (or many) special purpose process(es) could be crawling those other "list"-processes. Less crazy aproaches might make use of ets or mnesia.

Answer 4

Seeing erlang, and the erlang virtual machine, only supports immutable data it is impossible to build a circular list. If you were to build one yourself in some "illegal" way then it is not certain that the memory management could handle it properly.

Answer 5

Why yes you can ;)

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

And here is some crappy code to prove it

-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.