[erlang-questions] List comprehension puzzler

ok <>
Wed Sep 21 13:23:10 CEST 2016


By now I expect you've all seen my code which computes the
check sums and has no calls to length/1 at all.

I'd like to point out that it's straightforward to write

length_is([_|Xs], N) when N > 0 ->
    length_is(Xs, N-1);
length_is([], 0) ->
    true;
length_is(_, _) ->
    false.

which answers the question "is my first argument a list
whose length matches my second argument" in
O(min(|Xs|,N) time and to do

f(..., Xs, ...) ->
    f(..., Xs, length_is(Xs, 137), ...).

f(..., Xs, true, ...) ->
    % Xs is known to be a list of 137 elements
    ...

It's not much harder to write

length_between([_|Xs], L, U) when L > 0 ->
    length_between(Xs, L-1, U-1);
length_between([], L, U) ->
    L =< 0, 0 =< U;
length_between(_, _, _) ->
    false.

and use it the same way.  And of course, while it's
*nice* to do pattern matching in the head, we *do* have 'case'.

I was just marking some student code this afternoon
which called a Java method f(N) five times with the
same (large) value of N, the method having been
implemented to take O(N) time instead of the easily
achievable O(sort(N)).  A very slow program.  Yet
not, mathematically considered, a stupid one.  If
Java had (or for that matter, *could* have) the
notion of a "pure" method, constant subexpression
elimination could have helped.  (But not with O(N)
vs O(sort(N)).)



More information about the erlang-questions mailing list