[m-rev.] for review: make split_list/4, drop/3 and take/3 consistent.
Julien Fischer
jfischer at opturion.com
Sat Jun 4 17:15:32 AEST 2016
For review by anyone.
-----------------------------------------------------------------------
Make split_list/4, drop/3 and take/3 consistent.
Improve documentation and test coverage for the same.
library/list.m:
Change the behaviour of take/3 and drop/3 so they fail if their
first argument is negative. This makes them consistent with
the behaviour of split_list/4 and is arguably less surprising than
their current behaviour.
Make split_list/4 more efficient by not doing two comparison
operations per recursive call.
Re-implement det_drop/3 in terms of drop/3.
Fix the documentation of the failure condition of split_list/4,
take/3 and drop/3; all three omitted the description of what
happens if their first argument is negative.
Use 'N' rather than 'Len' for the name of the first argument
in the comments describing the above predicates; the latter
is ambiguous.
NEWS:
Announce the change in behaviour of take/3 and drop/3.
tests/hard_coded/list_split_take_drop.{m,exp}:
Test the behaviour of the above predicates and also check that the
expected relationships between them hold.
tests/hard_coded/Mmakefile:
Add the new test.
Julien.
diff --git a/NEWS b/NEWS
index 5628bb5..2ba389d 100644
--- a/NEWS
+++ b/NEWS
@@ -309,6 +309,9 @@ Changes to the Mercury standard library:
* The takewhile/4 predicate has been deprecated in the list module,
take_while/4 can be used instead.
+* The take/3 and drop/3 predicates in the list module have been modified
+ so that they fail if their first argument is less than zero.
+
* The following predicate and function in the builtin module have been
deprecated and will be removed in a future release:
diff --git a/library/list.m b/library/list.m
index 4a18bcc..9c33899 100644
--- a/library/list.m
+++ b/library/list.m
@@ -206,34 +206,35 @@
:- pred same_length3(list(T1)::in, list(T2)::in, list(T3)::in)
is semidet.
- % split_list(Len, List, Start, End):
+ % split_list(N, List, Start, End):
%
- % splits `List' into a prefix `Start' of length `Len', and a remainder
- % `End'. See also: take, drop and split_upto.
+ % splits `List' into a prefix `Start' of length `N', and a remainder
+ % `End'. Fails if `N' is not in 0 .. length(List).
+ % See also: take, drop and split_upto.
%
:- pred split_list(int::in, list(T)::in, list(T)::out, list(T)::out)
is semidet.
- % det_split_list(Len, List, Start, End):
+ % det_split_list(N, List, Start, End):
%
% A deterministic version of split_list, which aborts instead
- % of failing if Len > length(List).
+ % of failing if `N' is not in 0 .. length(List).
%
:- pred det_split_list(int::in, list(T)::in, list(T)::out, list(T)::out)
is det.
- % split_upto(Len, List, Start, End):
+ % split_upto(N, List, Start, End):
%
- % splits `List' into a prefix `Start' of length `min(Len, length(List))',
+ % splits `List' into a prefix `Start' of length `min(N, length(List))',
% and a remainder `End'. See also: split_list, take, drop.
%
:- pred split_upto(int::in, list(T)::in, list(T)::out, list(T)::out)
is det.
- % take(Len, List, Start):
+ % take(N, List, Start):
%
- % `Start' is the first `Len' elements of `List'. Fails if `List' has
- % less than `Len' elements. See also: split_list.
+ % `Start' is the first `Len' elements of `List'.
+ % Fails if `N' is not in 0 .. length(List).
%
:- pred take(int::in, list(T)::in, list(T)::out) is semidet.
@@ -251,18 +252,18 @@
:- pred take_upto(int::in, list(T)::in, list(T)::out) is det.
:- func take_upto(int, list(T)) = list(T).
- % drop(Len, List, End):
+ % drop(N, List, End):
%
- % `End' is the remainder of `List' after removing the first `Len' elements.
- % Fails if `List' does not have at least `Len' elements.
+ % `End' is the remainder of `List' after removing the first `N' elements.
+ % Fails if `N' is not in 0 .. length(List).
% See also: split_list.
%
:- pred drop(int::in, list(T)::in, list(T)::out) is semidet.
- % det_drop(Len, List, End):
+ % det_drop(N, List, End):
%
- % `End' is the remainder of `List' after removing the first `Len' elements.
- % Aborts if `List' does not have at least `Len' elements.
+ % `End' is the remainder of `List' after removing the first `N' elements.
+ % Aborts if `N' is not in 0 .. length(List).
% See also: split_list.
%
:- pred det_drop(int::in, list(T)::in, list(T)::out) is det.
@@ -2307,14 +2308,14 @@ zip2(As, [B | Bs], [B | Cs]) :-
%---------------------------------------------------------------------------%
split_list(N, List, Start, End) :-
- ( if N = 0 then
- Start = [],
- End = List
- else
- N > 0,
+ ( if N > 0 then
List = [Head | Tail],
list.split_list(N - 1, Tail, StartTail, End),
Start = [Head | StartTail]
+ else
+ N = 0,
+ Start = [],
+ End = List
).
det_split_list(N, List, Start, End) :-
@@ -2337,12 +2338,15 @@ split_upto(N, List, Start, End) :-
End = List
).
+%---------------------------------------------------------------------------%
+
take(N, Xs, InitialXs) :-
( if N > 0 then
Xs = [HeadX | TailXs],
list.take(N - 1, TailXs, InitialXsTail),
InitialXs = [HeadX | InitialXsTail]
else
+ N = 0,
InitialXs = []
).
@@ -2350,7 +2354,7 @@ det_take(N, Xs, InitialXs) :-
( if list.take(N, Xs, InitialXsPrime) then
InitialXs = InitialXsPrime
else
- unexpected($file, $pred, "not enough elements")
+ unexpected($file, $pred, "index out of range")
).
take_upto(N, Xs) = InitialXs :-
@@ -2363,29 +2367,6 @@ take_upto(N, Xs, InitialXs) :-
InitialXs = Xs
).
-drop(N, Xs, FinalXs) :-
- ( if N > 0 then
- Xs = [_ | Tail],
- list.drop(N - 1, Tail, FinalXs)
- else
- FinalXs = Xs
- ).
-
-det_drop(N, Xs, FinalXs) :-
- ( if N > 0 then
- (
- Xs = [_ | TailXs],
- list.det_drop(N - 1, TailXs, FinalXs)
- ;
- Xs = [],
- unexpected($module, $pred, "not enough elements")
- )
- else
- FinalXs = Xs
- ).
-
-%-----------------------------------------------------------------------%
-
take_while(_, [], [], []).
take_while(P, [X | Xs], Ins, Outs) :-
( if P(X) then
@@ -2411,6 +2392,24 @@ take_while(P, [X | Xs], Start) :-
take_while(P, Xs) = Start :-
take_while(P, Xs, Start).
+%---------------------------------------------------------------------------%
+
+drop(N, Xs, FinalXs) :-
+ ( if N > 0 then
+ Xs = [_ | Tail],
+ list.drop(N - 1, Tail, FinalXs)
+ else
+ N = 0,
+ FinalXs = Xs
+ ).
+
+det_drop(N, Xs, FinalXs) :-
+ ( if list.drop(N, Xs, FinalXsPrime) then
+ FinalXs = FinalXsPrime
+ else
+ unexpected($file, $pred, "index out of range")
+ ).
+
drop_while(_, [], []).
drop_while(P, [X | Xs], End) :-
( if P(X) then
diff --git a/tests/hard_coded/Mmakefile b/tests/hard_coded/Mmakefile
index ca2c3c1..979cf26 100644
--- a/tests/hard_coded/Mmakefile
+++ b/tests/hard_coded/Mmakefile
@@ -183,6 +183,7 @@ ORDINARY_PROGS = \
lexer_bigint \
lexer_zero \
list_series_int \
+ list_split_take_drop \
lookup_disj \
lookup_switch_simple \
lookup_switch_simple_bitvec \
diff --git a/tests/hard_coded/list_split_take_drop.exp b/tests/hard_coded/list_split_take_drop.exp
index e69de29..5477947 100644
--- a/tests/hard_coded/list_split_take_drop.exp
+++ b/tests/hard_coded/list_split_take_drop.exp
@@ -0,0 +1,76 @@
+split_list(int.min_int, []) ===> <<FALSE>>
+drop(int.min_int, []) ===> <<FALSE>>
+take(int.min_int, []) ===> <<FALSE>>
+
+split_list(int.min_int, [111]) ===> <<FALSE>>
+drop(int.min_int, [111]) ===> <<FALSE>>
+take(int.min_int, [111]) ===> <<FALSE>>
+
+split_list(int.min_int, [111, 222]) ===> <<FALSE>>
+drop(int.min_int, [111, 222]) ===> <<FALSE>>
+take(int.min_int, [111, 222]) ===> <<FALSE>>
+
+split_list(-1, []) ===> <<FALSE>>
+drop(-1, []) ===> <<FALSE>>
+take(-1, []) ===> <<FALSE>>
+
+split_list(-1, [111]) ===> <<FALSE>>
+drop(-1, [111]) ===> <<FALSE>>
+take(-1, [111]) ===> <<FALSE>>
+
+split_list(-1, [111, 222]) ===> <<FALSE>>
+drop(-1, [111, 222]) ===> <<FALSE>>
+take(-1, [111, 222]) ===> <<FALSE>>
+
+split_list(0, []) ===> ([], [])
+drop(0, []) ===> []
+take(0, []) ===> []
+
+split_list(0, [111]) ===> ([], [111])
+drop(0, [111]) ===> [111]
+take(0, [111]) ===> []
+
+split_list(0, [111, 222]) ===> ([], [111, 222])
+drop(0, [111, 222]) ===> [111, 222]
+take(0, [111, 222]) ===> []
+
+split_list(1, []) ===> <<FALSE>>
+drop(1, []) ===> <<FALSE>>
+take(1, []) ===> <<FALSE>>
+
+split_list(1, [111]) ===> ([111], [])
+drop(1, [111]) ===> []
+take(1, [111]) ===> [111]
+
+split_list(1, [111, 222]) ===> ([111], [222])
+drop(1, [111, 222]) ===> [222]
+take(1, [111, 222]) ===> [111]
+
+split_list(2, []) ===> <<FALSE>>
+drop(2, []) ===> <<FALSE>>
+take(2, []) ===> <<FALSE>>
+
+split_list(2, [111]) ===> <<FALSE>>
+drop(2, [111]) ===> <<FALSE>>
+take(2, [111]) ===> <<FALSE>>
+
+split_list(2, [111, 222]) ===> ([111, 222], [])
+drop(2, [111, 222]) ===> []
+take(2, [111, 222]) ===> [111, 222]
+
+split_list(2, [111, 222, 333]) ===> ([111, 222], [333])
+drop(2, [111, 222, 333]) ===> [333]
+take(2, [111, 222, 333]) ===> [111, 222]
+
+split_list(int.max_int, []) ===> <<FALSE>>
+drop(int.max_int, []) ===> <<FALSE>>
+take(int.max_int, []) ===> <<FALSE>>
+
+split_list(int.max_int, [111]) ===> <<FALSE>>
+drop(int.max_int, [111]) ===> <<FALSE>>
+take(int.max_int, [111]) ===> <<FALSE>>
+
+split_list(int.max_int, [111, 222]) ===> <<FALSE>>
+drop(int.max_int, [111, 222]) ===> <<FALSE>>
+take(int.max_int, [111, 222]) ===> <<FALSE>>
+
diff --git a/tests/hard_coded/list_split_take_drop.m b/tests/hard_coded/list_split_take_drop.m
index e69de29..3a4cdaa 100644
--- a/tests/hard_coded/list_split_take_drop.m
+++ b/tests/hard_coded/list_split_take_drop.m
@@ -0,0 +1,126 @@
+%---------------------------------------------------------------------------%
+% vim: ts=4 sw=4 et ft=mercury
+%---------------------------------------------------------------------------%
+
+:- module list_split_take_drop.
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+:- implementation.
+
+:- import_module assoc_list.
+:- import_module int.
+:- import_module list.
+:- import_module maybe.
+:- import_module pair.
+:- import_module string.
+
+main(!IO) :-
+ list.foldl(run_test, tests, !IO).
+
+:- pred run_test(pair(int, list(int))::in, io::di, io::uo) is det.
+
+run_test(N - List, !IO) :-
+ NStr = describe_int(N),
+ ListStr = string(List),
+
+ % Test split_list/4.
+ %
+ io.format("split_list(%s, %s) ===> ", [s(NStr), s(ListStr)], !IO),
+ ( if list.split_list(N, List, SplitStart, SplitEnd) then
+ io.format("(%s, %s)\n", [s(string(SplitStart)), s(string(SplitEnd))], !IO),
+ MaybeSplitStart = yes(SplitStart),
+ MaybeSplitEnd = yes(SplitEnd)
+ else
+ write_false(!IO),
+ MaybeSplitStart = no,
+ MaybeSplitEnd = no
+ ),
+
+ % Test drop/3.
+ %
+ io.format("drop(%s, %s) ===> ", [s(NStr), s(ListStr)], !IO),
+ ( if list.drop(N, List, DropEnd) then
+ io.format("%s\n", [s(string(DropEnd))], !IO),
+ MaybeDropEnd = yes(DropEnd)
+ else
+ write_false(!IO),
+ MaybeDropEnd = no
+ ),
+
+ % Test take/3.
+ %
+ io.format("take(%s, %s) ===> ", [s(NStr), s(ListStr)], !IO),
+ ( if list.take(N, List, TakeStart) then
+ io.format("%s\n", [s(string(TakeStart))], !IO),
+ MaybeTakeStart = yes(TakeStart)
+ else
+ write_false(!IO),
+ MaybeTakeStart = no
+ ),
+
+ % Check that drop(N, List, End) <=> split_list(N, List, _, End).
+ %
+ ( if MaybeSplitEnd = MaybeDropEnd then
+ true
+ else
+ io.format("ERROR: split_list/4 and drop/3 differ for (%s, %s)\n",
+ [s(NStr), s(ListStr)], !IO)
+ ),
+
+ % Check that take(N, List, Start) <=> split_list(N, List, Start, _)
+ %
+ ( if MaybeSplitStart = MaybeTakeStart then
+ true
+ else
+ io.format("ERROR: split_list/4 and take/3 differ for (%s, %s)\n",
+ [s(NStr), s(ListStr)], !IO)
+ ),
+ io.nl(!IO).
+
+:- func tests = assoc_list(int, list(int)).
+
+tests = [
+ int.min_int - [],
+ int.min_int - [111],
+ int.min_int - [111, 222],
+ -1 - [],
+ -1 - [111],
+ -1 - [111, 222],
+ 0 - [],
+ 0 - [111],
+ 0 - [111, 222],
+ 1 - [],
+ 1 - [111],
+ 1 - [111, 222],
+ 2 - [],
+ 2 - [111],
+ 2 - [111, 222],
+ 2 - [111, 222, 333],
+ int.max_int - [],
+ int.max_int - [111],
+ int.max_int - [111, 222]
+].
+
+:- func describe_int(int) = string.
+
+describe_int(N) =
+ ( if N = int.min_int then
+ "int.min_int"
+ else if N = int.max_int then
+ "int.max_int"
+ else
+ int_to_string(N)
+ ).
+
+:- pred write_false(io::di, io::uo) is det.
+
+write_false(!IO) :-
+ io.write_string("<<FALSE>>\n", !IO).
+
+%---------------------------------------------------------------------------%
+:- end_module list_split_take_drop.
+%---------------------------------------------------------------------------%
More information about the reviews
mailing list