push_element/2 - efficient sliding window

Ulf Wiger (AL/EAB) <>
Fri Aug 12 11:05:48 CEST 2005


Vlad Dumitrescu wrote:
>
> Ulf Wiger wrote:
> > tag_search([{Tag | _} = T|_], Tag) ->
> >     {value, T};
> > ...
> > 
> > That is, describing the "tail" of a tuple in a manner
> > similar to that of lists. This form is actually used
> > in some places in the documentation! Most likely because
> > it's very convenient. It could also be used to improve
> > backwards compatibility, since new elements in a tuple
> > are usually added last to preserve order.
> 
> Dou you think it should also work as a constructor?
> 	Tuple2 = { Elem | Tuple1}
> 
> Elegance would require it, but it would be quite inefficient 
> to use tuples in this way (where in fact lists are needed) 
> because one needs to copy the tuple contents, whereas adding 
> to the head of a list is constant time.

I'd be perfectly happy to have it as syntactic sugar for

tag_search([T|_], Tag) when element(1, T) == Tag ->
   {value, T};


In this particular example, it's only a marginal improvement,
but in other cases, it could be a significant boon:


(Just grabbing some code from stdlib -- erl_lint.erl:


pattern({record_field,Line,_,_}=M, _Vt, _Old, _Bvt, St0) ->
    case expand_package(M, St0) of
        {error, St1} ->
            {[],[],add_error(Line, illegal_expr, St1)};
        {_, St1} ->
            {[],[],St1}
    end;


Imagine wanting to add an "annotations" element to tuples in
the parse tree (or perhaps column numbers). It's a silly idea,
since it would require a total rewrite of compiler and linter,
and a load of other modules as well.

What if we could rewrite the above code as:

pattern({record_field,Line|_}=M, _Vt, _Old, _Bvt, St0) ->
    case expand_package(M, St0) of
        {error, St1} ->
            {[],[],add_error(Line, illegal_expr, St1)};
        {_, St1} ->
            {[],[],St1}
    end;


But this function didn't modify the tuple, so it's an easy
case.

pattern({op,_Line,'++',{cons,Li,{char,_L2,_C},T},R}, Vt, Old, Bvt, St) ->
    pattern({op,Li,'++',T,R}, Vt, Old, Bvt, St);    %Char unimportant here

would at first become:

pattern({op,_Line,'++',{cons,Li,{char,_L2,_C|_},T|_},R|Rest}, Vt, Old, Bvt, St) ->
    pattern({op,Li,'++',T,R|Rest}, Vt, Old, Bvt, St);    %Char unimportant here


Then, yes, it would have to work as a constructor too, but 
with the meaning of:

pattern(P, Vt, Old, Bvt, St) when element(1,P) == op, 
                                  element(2,P) == '++',
                                  element(1,element(3,P))==cons,
                                  element(1,element(3,element(3,P)))==char ->
    Cons = element(3, P),
    Li = element(2, Cons),
    T = element(3, Cons),
    P1 = setelement(2, setelement(4, P, T), Li),
    pattern(P1, Vt, Old, Bvt, St);   %Char unimportant here


That is, not modifying the lenght of the tuple, but rather
as syntactic sugar for what would otherwise be a cascade of 
setelement/3 calls.

(which may also serve to illustrate why nobody in his right mind
writes code like this today.)

/Uffe



More information about the erlang-questions mailing list