[m-rev.] for review: list.condense/2 with constant stack usage

[Julien Fischer]

Branches: main, 11.07

Replace the current implementation of list.condense/2 with one that uses
constant stack space.  The existing implementation causes a stack overflow if
the input argument contains just over a million sublists -- in G12's mzn2fzn
tool list.condense/2 can sometimes be called with a much larger input argument.
The new version has higher constant factors but the performance difference only
becomes significant at the point where you need to worry about stack usage
anyway.

Julien.

Index: library/list.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/list.m,v
retrieving revision 1.203
diff -u -r1.203 list.m
--- library/list.m	26 Sep 2011 07:08:57 -0000	1.203
+++ library/list.m	15 Nov 2011 03:28:25 -0000
@@ -1788,11 +1788,17 @@
  list.condense(Xss) = Ys :-
      list.condense(Xss, Ys).

-list.condense([], []).
-list.condense([L | Ls], R) :-
-    list.condense(Ls, R1),
-    list.append(L, R1, R).
-
+list.condense(Xss, Ys) :-
+    list.reverse(Xss, RevXss),
+    list.condense_2(RevXss, [], Ys).
+
+:- pred list.condense_2(list(list(T))::in, list(T)::in, list(T)::out) is det.
+
+list.condense_2([], !Ys).
+list.condense_2([L | Ls], !Ys) :-
+    list.append(L, !Ys),
+    list.condense_2(Ls, !Ys).
+
  %-----------------------------------------------------------------------------%

  list.same_length([], []).

--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------