[erlang-questions] queue:split/2 unsafe!

Richard A. O'Keefe <>
Wed Apr 10 02:21:58 CEST 2013


There are actually two different things that someone might want to do:

(X) I want *exactly* N items from this sequence:
	n -> seq -> (pref, suff) where pref++suff == seq && #pref == n

(Y) I want *at most* N items from this sequence:
	n -> seq -> (pref, suff) where pref++suff == seq &&
				       #pref = min(#seq, n)

If you want exactly N items and there are not N items available,
that's an error.
If you want at most N items and there are not N items available,
that is *not* an error, it's something you had in mind when you asked.

I agree with Fred Herbert that existing functions designed for use
case (X) should not be changed; that guarantee that you got as much
as you asked for is too precious to lose.

I also agree with Ivan Uemlianin that use case (Y) is also important
enough to support (think of Unix read(2)).

I disagree with him that 'safe_split' is a good name for use case (Y).
There are plenty of situations where (X) is the safe alternative.

So why not add

.. in lists.erl ..

%% split_at_most(N, L) returns {P, S}
%% such that L = P++S and length(P) == min(N, length(L)).
%% If you need length(P) == N exactly, you must use split/2.
%% This is for use when you are happy with a short result.

-spec(split_at_most/2 :: (non_neg_integer(),[T]) -> {[T],[T]}).

split_at_most(N, L) when is_integer(N), N >= 0, is_list(L) ->
    split_at_most(N, L, []).

split_at_most(N, [H|T], PR) when N > 0 ->
    split_at_most(N-1, T, [H|PR]);
split_at_most(_, S, PR) ->
    {reverse(PR), S}.

Does anyone else find it confusing that it's "listS.erl" (plural)
but "queue.erl" (singular)?  Is there only one queue?  

%% split_at_most(N, Q) returns {P, S}
%% such that P and S are queues and concatenating S after P
%% gives you a queue with the same elements as Q in the same
%% logical order, and length(P) == min(N, length(Q)).
%% If you need length(P) == N exactly, you must use split/2.
%% This is for use when you are happy with a short result.

-spec(split_at_most/2 :: (non_neg_integer(),{[T],[T]}) ->
                         {{[T],[T]},{[T],[T]}}).

split_at_most(N, {Back,Front})
  when is_integer(N), N >= 0, is_list(Back), is_list(Front) ->
    LF = length(Front),
    if LF >= N ->
       {PF, SF} = lists:split_at_most(N, Front),
       {f2r(PF), {Back,SF}}
     ; true ->
       {PB, SB} = lists:split_at_most(N-LF, lists:reverse(Back)),
       {f2r(Front++PB), f2r(SB)}
    end.

This code has been tested.

However, looking through queue.erl has convinced me, the next
time I need queues, to write my own module.




More information about the erlang-questions mailing list