Valkertown Blog

I used to write about electronics…

Valkertown Blog header image 2

Writting Circular Lists in Erlang

March 18th, 2009 by Carlos Perilla

Well I have been struggling to find/create a circular buffer(list to be exact) on erlang, but I’m still not satisfied, I have hacked this:

  1. [_P | T ] = lists:reverse(O),
  2.     N = [ V | lists:reverse(T)],

To insert V in the head and remove P from the tail. But can you see the problem with that: Two list reverse operations, that to me seems like expensive operations, maybe I’m not understanding fully the erlang’s lists module but I can’t find other way to do this using lists.

I know several other ways to implement circular buffers using arrays, one even might think using queues for what I need this buffer, but I need to remove any index from the buffer so lists makes a lot more sense than any other data structure.

Well I’ll be glad if someone enlightens me with another solution
EOP

Tags:   · Comments

  • nonme
    keep two lists {A, B} one in normal order the other reversed
    To move forward do this

    forward({[H|T],B}) -> {T, [H|B]};
    forward({[], B}) -> forward({reverse(B),[]})

    bawards is the opposite
  • Thanks, I'll give it a try and do a benchmark to see if It's better to
    the other solution in the above comments.
  • The key is to process the list in one pass. So if I read your intent above correctly then the following should work:

    %% append the Push element to the beginning of the list while dropping the last element
    circular(List, Push) ->
    [Push] ++ drop_last(List).

    %% drop the last element from the list
    drop_last([_]) ->
    [];
    drop_last([H|T]) ->
    [H | drop_last(T)].
  • Nice, I'm just repeating what I have read so far but

    [Push] ++ drop_last(List)

    Wouldn't it be better written as:

    [ Push | drop_last(List)]

    Anyway, ++ is discouraged since it makes a copy of the left operator and with long lists it would be highly inefficient, in this case it wouldn't be much of a problem but I still like more how the second one looks.

    Thank you a lot for this idea, I'm guessing it's probably the best way to write it on erlang.
  • yeah ++ is less efficient. [Push | drop_last(List)] would be better. That's what I get for coding when I'm tired. but the basic concept is the same.
blog comments powered by Disqus