[m-rev.] for review: Make some cord functions tail recursive.
Peter Wang
novalazy at gmail.com
Thu Jun 13 14:14:05 AEST 2013
On Thu, 13 Jun 2013 12:43:08 +1000, Peter Wang <novalazy at gmail.com> wrote:
> On Thu, 13 Jun 2013 12:30:14 +1000 (EST), Julien Fischer <jfischer at opturion.com> wrote:
> >
> > On Thu, 13 Jun 2013, Peter Wang wrote:
> >
> > > Branches: 13.05, master
> > > ---
> > >
> > > Make these functions tail recursive:
> > >
> > > cord.list
> > > cord.rev_list
> > > cord.cord_list_to_cord
> > > cord.cord_list_to_list
> > >
> > > library/cord.m:
> > > As above.
> >
> > I assume we have tests in the test suite that test the functionality of
> > the above?
>
> There is only one test case and it is severely deficient. I'm trying to
> write another one now.
For review.
---
Add test case for cords.
Test the recently changed functions more comprehensively:
cord.list, cord.rev_list, cord.cord_list_to_cord, cord.cord_list_to_list.
The existing test_cord.m is deficient, and did not reveal a bug in the
previous implementation of cord.rev_list (the non-tail-recursive one).
tests/hard_coded/Mmakefile:
tests/hard_coded/test_cord2.exp:
tests/hard_coded/test_cord2.m:
Add test case.
diff --git a/tests/hard_coded/Mmakefile b/tests/hard_coded/Mmakefile
index 026e01f..acecc02 100644
--- a/tests/hard_coded/Mmakefile
+++ b/tests/hard_coded/Mmakefile
@@ -301,6 +301,7 @@ ORDINARY_PROGS= \
term_to_univ_test \
test234_sorted_insert \
test_cord \
+ test_cord2 \
test_imported_no_tag \
test_keys_and_values \
test_pretty_printer \
diff --git a/tests/hard_coded/test_cord2.exp b/tests/hard_coded/test_cord2.exp
new file mode 100644
index 0000000..e52ed51
--- /dev/null
+++ b/tests/hard_coded/test_cord2.exp
@@ -0,0 +1,121 @@
+Test list and rev_list
+empty_cord
+[]
+[]
+nonempty_cord(unit_node(1))
+[1]
+[1]
+nonempty_cord(list_node(2, [3, 4]))
+[2, 3, 4]
+[4, 3, 2]
+nonempty_cord(branch_node(unit_node(1), unit_node(1)))
+[1, 1]
+[1, 1]
+nonempty_cord(branch_node(unit_node(1), list_node(2, [3, 4])))
+[1, 2, 3, 4]
+[4, 3, 2, 1]
+nonempty_cord(branch_node(unit_node(1), branch_node(unit_node(1), unit_node(1))))
+[1, 1, 1]
+[1, 1, 1]
+nonempty_cord(branch_node(unit_node(1), branch_node(unit_node(1), list_node(2, [3, 4]))))
+[1, 1, 2, 3, 4]
+[4, 3, 2, 1, 1]
+nonempty_cord(branch_node(unit_node(1), branch_node(list_node(2, [3, 4]), unit_node(1))))
+[1, 2, 3, 4, 1]
+[1, 4, 3, 2, 1]
+nonempty_cord(branch_node(unit_node(1), branch_node(list_node(2, [3, 4]), list_node(2, [3, 4]))))
+[1, 2, 3, 4, 2, 3, 4]
+[4, 3, 2, 4, 3, 2, 1]
+nonempty_cord(branch_node(list_node(2, [3, 4]), unit_node(1)))
+[2, 3, 4, 1]
+[1, 4, 3, 2]
+nonempty_cord(branch_node(list_node(2, [3, 4]), list_node(2, [3, 4])))
+[2, 3, 4, 2, 3, 4]
+[4, 3, 2, 4, 3, 2]
+nonempty_cord(branch_node(list_node(2, [3, 4]), branch_node(unit_node(1), unit_node(1))))
+[2, 3, 4, 1, 1]
+[1, 1, 4, 3, 2]
+nonempty_cord(branch_node(list_node(2, [3, 4]), branch_node(unit_node(1), list_node(2, [3, 4]))))
+[2, 3, 4, 1, 2, 3, 4]
+[4, 3, 2, 1, 4, 3, 2]
+nonempty_cord(branch_node(list_node(2, [3, 4]), branch_node(list_node(2, [3, 4]), unit_node(1))))
+[2, 3, 4, 2, 3, 4, 1]
+[1, 4, 3, 2, 4, 3, 2]
+nonempty_cord(branch_node(list_node(2, [3, 4]), branch_node(list_node(2, [3, 4]), list_node(2, [3, 4]))))
+[2, 3, 4, 2, 3, 4, 2, 3, 4]
+[4, 3, 2, 4, 3, 2, 4, 3, 2]
+nonempty_cord(branch_node(branch_node(unit_node(1), unit_node(1)), unit_node(1)))
+[1, 1, 1]
+[1, 1, 1]
+nonempty_cord(branch_node(branch_node(unit_node(1), unit_node(1)), list_node(2, [3, 4])))
+[1, 1, 2, 3, 4]
+[4, 3, 2, 1, 1]
+nonempty_cord(branch_node(branch_node(unit_node(1), unit_node(1)), branch_node(unit_node(1), unit_node(1))))
+[1, 1, 1, 1]
+[1, 1, 1, 1]
+nonempty_cord(branch_node(branch_node(unit_node(1), unit_node(1)), branch_node(unit_node(1), list_node(2, [3, 4]))))
+[1, 1, 1, 2, 3, 4]
+[4, 3, 2, 1, 1, 1]
+nonempty_cord(branch_node(branch_node(unit_node(1), unit_node(1)), branch_node(list_node(2, [3, 4]), unit_node(1))))
+[1, 1, 2, 3, 4, 1]
+[1, 4, 3, 2, 1, 1]
+nonempty_cord(branch_node(branch_node(unit_node(1), unit_node(1)), branch_node(list_node(2, [3, 4]), list_node(2, [3, 4]))))
+[1, 1, 2, 3, 4, 2, 3, 4]
+[4, 3, 2, 4, 3, 2, 1, 1]
+nonempty_cord(branch_node(branch_node(unit_node(1), list_node(2, [3, 4])), unit_node(1)))
+[1, 2, 3, 4, 1]
+[1, 4, 3, 2, 1]
+nonempty_cord(branch_node(branch_node(unit_node(1), list_node(2, [3, 4])), list_node(2, [3, 4])))
+[1, 2, 3, 4, 2, 3, 4]
+[4, 3, 2, 4, 3, 2, 1]
+nonempty_cord(branch_node(branch_node(unit_node(1), list_node(2, [3, 4])), branch_node(unit_node(1), unit_node(1))))
+[1, 2, 3, 4, 1, 1]
+[1, 1, 4, 3, 2, 1]
+nonempty_cord(branch_node(branch_node(unit_node(1), list_node(2, [3, 4])), branch_node(unit_node(1), list_node(2, [3, 4]))))
+[1, 2, 3, 4, 1, 2, 3, 4]
+[4, 3, 2, 1, 4, 3, 2, 1]
+nonempty_cord(branch_node(branch_node(unit_node(1), list_node(2, [3, 4])), branch_node(list_node(2, [3, 4]), unit_node(1))))
+[1, 2, 3, 4, 2, 3, 4, 1]
+[1, 4, 3, 2, 4, 3, 2, 1]
+nonempty_cord(branch_node(branch_node(unit_node(1), list_node(2, [3, 4])), branch_node(list_node(2, [3, 4]), list_node(2, [3, 4]))))
+[1, 2, 3, 4, 2, 3, 4, 2, 3, 4]
+[4, 3, 2, 4, 3, 2, 4, 3, 2, 1]
+nonempty_cord(branch_node(branch_node(list_node(2, [3, 4]), unit_node(1)), unit_node(1)))
+[2, 3, 4, 1, 1]
+[1, 1, 4, 3, 2]
+nonempty_cord(branch_node(branch_node(list_node(2, [3, 4]), unit_node(1)), list_node(2, [3, 4])))
+[2, 3, 4, 1, 2, 3, 4]
+[4, 3, 2, 1, 4, 3, 2]
+nonempty_cord(branch_node(branch_node(list_node(2, [3, 4]), unit_node(1)), branch_node(unit_node(1), unit_node(1))))
+[2, 3, 4, 1, 1, 1]
+[1, 1, 1, 4, 3, 2]
+nonempty_cord(branch_node(branch_node(list_node(2, [3, 4]), unit_node(1)), branch_node(unit_node(1), list_node(2, [3, 4]))))
+[2, 3, 4, 1, 1, 2, 3, 4]
+[4, 3, 2, 1, 1, 4, 3, 2]
+nonempty_cord(branch_node(branch_node(list_node(2, [3, 4]), unit_node(1)), branch_node(list_node(2, [3, 4]), unit_node(1))))
+[2, 3, 4, 1, 2, 3, 4, 1]
+[1, 4, 3, 2, 1, 4, 3, 2]
+nonempty_cord(branch_node(branch_node(list_node(2, [3, 4]), unit_node(1)), branch_node(list_node(2, [3, 4]), list_node(2, [3, 4]))))
+[2, 3, 4, 1, 2, 3, 4, 2, 3, 4]
+[4, 3, 2, 4, 3, 2, 1, 4, 3, 2]
+nonempty_cord(branch_node(branch_node(list_node(2, [3, 4]), list_node(2, [3, 4])), unit_node(1)))
+[2, 3, 4, 2, 3, 4, 1]
+[1, 4, 3, 2, 4, 3, 2]
+nonempty_cord(branch_node(branch_node(list_node(2, [3, 4]), list_node(2, [3, 4])), list_node(2, [3, 4])))
+[2, 3, 4, 2, 3, 4, 2, 3, 4]
+[4, 3, 2, 4, 3, 2, 4, 3, 2]
+nonempty_cord(branch_node(branch_node(list_node(2, [3, 4]), list_node(2, [3, 4])), branch_node(unit_node(1), unit_node(1))))
+[2, 3, 4, 2, 3, 4, 1, 1]
+[1, 1, 4, 3, 2, 4, 3, 2]
+nonempty_cord(branch_node(branch_node(list_node(2, [3, 4]), list_node(2, [3, 4])), branch_node(unit_node(1), list_node(2, [3, 4]))))
+[2, 3, 4, 2, 3, 4, 1, 2, 3, 4]
+[4, 3, 2, 1, 4, 3, 2, 4, 3, 2]
+nonempty_cord(branch_node(branch_node(list_node(2, [3, 4]), list_node(2, [3, 4])), branch_node(list_node(2, [3, 4]), unit_node(1))))
+[2, 3, 4, 2, 3, 4, 2, 3, 4, 1]
+[1, 4, 3, 2, 4, 3, 2, 4, 3, 2]
+nonempty_cord(branch_node(branch_node(list_node(2, [3, 4]), list_node(2, [3, 4])), branch_node(list_node(2, [3, 4]), list_node(2, [3, 4]))))
+[2, 3, 4, 2, 3, 4, 2, 3, 4, 2, 3, 4]
+[4, 3, 2, 4, 3, 2, 4, 3, 2, 4, 3, 2]
+
+Test cord_list_to_cord and cord_list_to_list
+done.
diff --git a/tests/hard_coded/test_cord2.m b/tests/hard_coded/test_cord2.m
new file mode 100644
index 0000000..0e3c1b8
--- /dev/null
+++ b/tests/hard_coded/test_cord2.m
@@ -0,0 +1,111 @@
+:- module test_cord2.
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module cord.
+:- import_module int.
+:- import_module list.
+:- import_module require.
+:- import_module solutions.
+
+%-----------------------------------------------------------------------------%
+
+main(!IO) :-
+ io.write_string("Test list and rev_list\n", !IO),
+ solutions(gen_cord3, Cords),
+ list.foldl(test_list_and_rev_list, Cords, !IO),
+
+ io.write_string("\nTest cord_list_to_cord and cord_list_to_list\n", !IO),
+ solutions(gen_cord_list, CordLists),
+ list.foldl(test_cord_list_funcs, CordLists, !IO),
+ io.write_string("done.\n", !IO).
+
+:- pred test_list_and_rev_list(cord(int)::in, io::di, io::uo) is det.
+
+test_list_and_rev_list(Cord, !IO) :-
+ io.write(Cord, !IO),
+ io.nl(!IO),
+
+ List = list(Cord),
+ io.write(List, !IO),
+ io.nl(!IO),
+
+ RevList = rev_list(Cord),
+ io.write(RevList, !IO),
+ io.nl(!IO),
+
+ expect(unify(length(List), length(Cord)),
+ $module, $pred, "length(List) != length(Cord)"),
+
+ expect(unify(List, reverse(RevList)),
+ $module, $pred, "List != reverse(RevList)").
+
+:- pred test_cord_list_funcs(list(cord(int))::in, io::di, io::uo) is det.
+
+test_cord_list_funcs(Cords, !IO) :-
+ List1 = cord_list_to_list(Cords),
+ List2 = list(cord_list_to_cord(Cords)),
+ List3 = condense(map(list, Cords)),
+ expect(unify(List1, List2), $module, $pred, "List1 != List2"),
+ expect(unify(List1, List3), $module, $pred, "List1 != List3").
+
+%-----------------------------------------------------------------------------%
+
+:- pred gen_cord1(cord(int)::out) is multi.
+
+gen_cord1(empty).
+gen_cord1(singleton(1)).
+gen_cord1(from_list([2, 3, 4])).
+
+:- pred gen_cord2(cord(int)::out) is multi.
+
+gen_cord2(C) :-
+ (
+ gen_cord1(C)
+ ;
+ gen_cord1(A),
+ gen_cord1(B),
+ C = A ++ B
+ ).
+
+:- pred gen_cord3(cord(int)::out) is multi.
+
+gen_cord3(C) :-
+ (
+ gen_cord2(C)
+ ;
+ gen_cord2(A),
+ gen_cord2(B),
+ C = A ++ B
+ ).
+
+:- pred gen_cord_list(list(cord(int))::out) is multi.
+
+gen_cord_list(L) :-
+ (
+ L = []
+ ;
+ gen_cord2(A),
+ (
+ L = [A]
+ ;
+ gen_cord2(B),
+ (
+ L = [A, B]
+ ;
+ gen_cord2(C),
+ L = [A, B, C]
+ )
+ )
+ ).
+
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sts=4 sw=4 et
More information about the reviews
mailing list