[erlang-questions] List comprehension puzzler
ok
<>
Wed Sep 21 13:23:09 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