[erlang-questions] [Haskell-cafe] Haskell-cafe-cafe? Was: Re: Health effects

[Richard O'Keefe]

On 6 Oct 2008, at 1:54 am, Andrew Coppin wrote:

> Hi,
>
> If I have a list of a fixed size (say 10,000 elements).  What is the
> most efficient way to add a new item to the list and force out the old
> first element.

It depends on where you want to add the new item.
If you want it at the front, just

     New_List = [New_Item | tail(Old_List)]

is pretty hard to improve on.  If you want to add
the new item anywhere else, you will have to copy.

> I'm currently doing a double reverse trick, e.g. :
>
> Eshell V5.6.3  (abort with ^G)
> 1> L1 = ["A", "B", "C", "D", "E"].
> ["A","B","C","D","E"]
> 2> [_ | L2] = L1.
> ["A","B","C","D","E"]
> 3> lists:reverse(["F" | lists:reverse(L2)]).
> ["B","C","D","E","F"]

It appears that you are putting the new item at
the end, which is the costliest possible place
to put it.  You are also doing it in two
passes, when it can be done in one.

snoc(X, [Y|Ys]) -> [Y|snoc(X, Ys)];
snoc(X, [])     -> [X].

     New_List = snoc(New_Item, tail(Old_List))

The first question you have to ask yourself is
"why do I *care* where the new item goes?"

The second question you have to ask is "given
that I need a *sequence* where the order has to
be thus-and-such for such-and-such reasons,
is a list the right data structure to represent
this sequence?"

It may well be that a list is the wrong data structure.
Perhaps you need a queue (and it just so happens that
there is a 'queue' module in Erlang's stdlib).

Perhaps you need some more general sequence type,
in which case several of Chris Okasaki's functional
data structures have been converted to Erlang and
are available.