length() in guards

[Richard A. O'Keefe]

One of the perennial questions about Erlang is "can't we generalise
guards to allow any expression?"  The standard response is that the
guard tests and expressions are supposed to have certain properties.
And the standard retort to that is that length/1 does't have them.

A tiny restriction would tame length/1 in guards.
The restriction is
    "a call to length/1 may appear in a guard only as an entire
     operand of a comparison (==, /=, <, >=, >, <=, =:=, -/=)
     in which the other operand is not a call to length/1".

So
    length(X) == 4
would be allowed, but
    length(X)*2 == 8
would not be allowed.

This helps because computing length(X) requires time proportional
to the length of X, while computing length(X) <relop> N, where N
is an integer, requires time O(max(1,N)).  For example, the guard
test
    length(X) /= 2
can be evaluated in O(1) time, no matter how long X is.

Poking around in the Erlang sources, I've found that the majority
of uses of length/1 in a guard are equivalent to
    length(<var>) <relop> (<const> | <var> | size(<var>))

There are some exceptions.

There's a use of

    when length(<var1>) > length(<var2>)

that not only could be expressed without doing that, but would be
O(N) instead of O(N**2) if so expressed.

There's a use of

    when length(<var1>) == length(<var2>)

guarding a call to a function so that 'false' can be returned if the
lists aren't the same length, BUT that function would return 'false'
anyway in that case, AND <var1> is actually a loop invariant, so the
module doesn't really need to do this and would be faster if it didn't.

There's a function

f(E, F, [], false) when length(E) + length(F) == 8 ->
    list_to_tuple(reverse(E) ++ reverse(F));
f(E, F, [D,C,B,A], false) when length(E) + length(F) == 6 ->
    list_to_tuple(reverse(E) ++ reverse(F) ++ [A*256+B, C*256+D]);
f(E, F, [], true) when length(E)+length(F) =< 8 ->
    list_to_tuple(reverse(E) ++ zero(8-(length(E)+length(F))) ++ reverse(F));
f(E, F, [D,C,B,A], true) when length(E)+length(F) =< 6 ->
    list_to_tuple(reverse(E) ++ zero(6-(length(E)+length(F))) ++ reverse(F) ++
                  [A*256+B, C*256+D]).

which could be written as

f(E, F, X, B) ->
    list_to_tuple(f(E, F, X, B, length(E)+length(F))).

f(E, F, [], false, 8) ->
    reverse(E) ++ reverse(F);
f(E, F, [D,C,B,A], false, 6) ->
    reverse(E) ++ reverse(F) ++ [A*256+B,C*256+D];
f(E, F, [], true, N) when N =< 8 ->
    reverse(E) ++ zero(8-N) ++ reverse(F);
f(E, F, [D,C,B,A], true, N) when N =< 6 ->
    reverse(E) ++ zero(6-N) ++ reverse(F) ++ [A*256+B,C*256+D].

There's a
    when <var1> + length(<var2>) <relop> <var3>
that could be
    when length(<var2>) <relop> <var3> - <var1>

There's a function

f(X, Y) ->
    case lists:prefix(X, Y#field) of
        true when length(Y#field) > length(X) ->
            g(X, Y);
        false ->
            above
    end.

which could simply be

f(X, Y) ->
    case lists:proper_prefix(X, Y#field) of
        true  -> g(X, Y);
        false -> above
    end.

if only the lists module included

    proper_prefix([X|Prefix], [X|List]) ->
        proper_prefix(Prefix, List);
    proper_prefix([], [_|_]) -> true;
    proper_prefix(_, _) -> false.

which it should anyway.  When we look at g/2, we find

g(X, Y) when length(Y#field) == length(X) + 1 ->
    <stuff>;
g(X, Y) when length(Y#field) > length(X) + 1 ->
    <other stuff>.

So this pair of functions could be

f(X, Y) ->
    Delta = length(Y#field) - length(X),
    case lists:prefix(X, Y#field) of
        true when Delta > 0 ->
            g(X, Y, Delta);
	false ->
	    above
    end.

g(X, Y, Delta) when Delta == 1 ->
    <stuff>;
g(X, Y, Delta) when Delta > 1 ->
    <other stuff>.

There's also a function

f(X, Y) when length(X) == length(Y) ->
    <stuff 1>;
f(X, Y) when length(X) > length(Y) ->
    <stuff 2>;
f(X, Y) when length(X) < length(Y) ->
    <stuff 3>.

This is obviously inefficient; it could so easily have been

f(X, Y) ->
    Delta is length(X) - length(Y),
    if Delta < 0 -> <stuff 3>;
       Delta > 0 -> <stuff 2>;
       Delta ==0 -> <stuff 1>
    end.

So everywhere I look, either the guards already conform to this
restriction, or the code would be more efficient if it did conform,
and could be at least as clear.

What do people think?