[erlang-questions] per function/process locals

Thu May 3 02:55:33 CEST 2007

On 2 May 2007, at 11:21 pm, Ulf Wiger (TN/EAB) wrote
[that instead of doing]
> init_state(L) ->
>   lists:foldl(
>     fun({a, A}, S) -> S#st{a = A};
>        ({b, B}, S) -> S#st{b = B};
>        ...
>     end, #st{}, L).
[he tends to do]
>   [A, B, C, D] =
>     [proplists:get_value(K,L) ||
>       K <- [a, b, c, d]],
>   #st{a = A, b = B, c = C, d = D}

This is a rather interesting example, because it shows a clear trade- 
Suppose there are V "variables".  We expect that the list will contain
each at most once; the worst case is when they all appear.

The first algorithm does one pass -- O(V) work for traversal -- building
a new record (memory size V+2 words at least) on each iteration, for a
total of O(V**2) time and O(V**2) space turned over.
The second algorithm does V passes -- O(V**2) work for traversal -- but
each pass builds only a single cons cell -- O(V) space --.  For large V,
it is better to sort the list L -- O(V.lg V) time and space -- and then
do a merge -- O(V) time and space --.  This is basically what
list_to_frame/1 does in my "frames" proposal (which is not entirely
unlike Joe Armstrong's "proper structs").  See
for details.

It would be interesting to see more examples where people want "many"
"variables" in a loop, to discover whether they could be handled in the
source language by multiple loops each working with fewer variables.
If so, compiler support for loop fusion (which would be a very nice
thing to have anyway) might do more for us than special syntax.

More information about the erlang-questions mailing list