[m-rev.] for review: add more operations on cords

[Julien Fischer]

For review by anyone.

--------------------

Add more operations on cords.

library/cord.m:
     Add is_singleton/2, foldr2/6 and foldr3/8.

NEWS:
      Announce the above additions.

tests/hard_coded/Mmakefile:
tests/hard_coded/test_cord3.{m,exp}:
      Add a test of is_singleton/2 (and is_empty/1).

Julien.

diff --git a/NEWS b/NEWS
index 9e57774..539149e 100644
--- a/NEWS
+++ b/NEWS
@@ -62,6 +62,14 @@ Changes to the Mercury standard library
      - func `promise_only_solution/1`
      - pred `promise_only_solution_io/4`

+### Changes to the `cord` module
+
+* The following predicates have been added:
+
+    - pred `foldr2/6`
+    - pred `foldr3/8`
+    - pred `is_singleton/2`
+
  ### Changes to the `diet` module

  * The following obsolete predicate has been removed:
diff --git a/library/cord.m b/library/cord.m
index b211e1c..d7307f3 100644
--- a/library/cord.m
+++ b/library/cord.m
@@ -2,7 +2,7 @@
  % vim: ft=mercury ts=4 sw=4 et
  %---------------------------------------------------------------------------%
  % Copyright (C) 2002-2011 The University of Melbourne.
-% Copyright (C) 2013-2018 The Mercury team.
+% Copyright (C) 2013-2018, 2021-2022 The Mercury team.
  % This file is distributed under the terms specified in COPYING.LIB.
  %---------------------------------------------------------------------------%
  %
@@ -58,6 +58,10 @@
      %
  :- func singleton(T) = cord(T).

+    % is_singleton(C, X) <=> list(C) = [X].
+    %
+:- pred is_singleton(cord(T)::in, T::out) is semidet.
+
      % list(from_list(Xs)) = Xs
      % An O(1) operation.
      %
@@ -251,6 +255,42 @@
  :- mode foldr_pred(in(pred(in, mdi, muo) is semidet), in, mdi, muo) is semidet.
  :- mode foldr_pred(in(pred(in, di, uo) is semidet), in, di, uo) is semidet.

+    % foldr2(P, C, !AccA, !AccB):
+    %
+    % Equivalent to list.foldr2(P, list(C), !AccA, !AccB), but faster.
+    %
+:- pred foldr2(pred(T, A, A, B, B), cord(T), A, A, B, B).
+:- mode foldr2(in(pred(in, in, out, in, out) is det), in, in, out,
+    in, out) is det.
+:- mode foldr2(in(pred(in, in, out, mdi, muo) is det), in, in, out,
+    mdi, muo) is det.
+:- mode foldr2(in(pred(in, in, out, di, uo) is det), in, in, out,
+    di, uo) is det.
+:- mode foldr2(in(pred(in, in, out, in, out) is semidet), in, in, out,
+    in, out) is semidet.
+:- mode foldr2(in(pred(in, in, out, mdi, muo) is semidet), in, in, out,
+    mdi, muo) is semidet.
+:- mode foldr2(in(pred(in, in, out, di, uo) is semidet), in, in, out,
+    di, uo) is semidet.
+
+    % foldr3(P, C, !AccA, !AccB,! AccC):
+    %
+    % Equivalent to list.foldr3(P, list(C), !AccA, !AccB, !AccC), but faster.
+    %
+:- pred foldr3(pred(T, A, A, B, B, C, C), cord(T), A, A, B, B, C, C).
+:- mode foldr3(in(pred(in, in, out, in, out, in, out) is det), in,
+    in, out, in, out, in, out) is det.
+:- mode foldr3(in(pred(in, in, out, in, out, mdi, muo) is det), in,
+    in, out, in, out, mdi, muo) is det.
+:- mode foldr3(in(pred(in, in, out, in, out, di, uo) is det), in,
+    in, out, in, out, di, uo) is det.
+:- mode foldr3(in(pred(in, in, out, in, out, in, out) is semidet), in,
+    in, out, in, out, in, out) is semidet.
+:- mode foldr3(in(pred(in, in, out, in, out, mdi, muo) is semidet), in,
+    in, out, in, out, mdi, muo) is semidet.
+:- mode foldr3(in(pred(in, in, out, in, out, di, uo) is semidet), in,
+    in, out, in, out, di, uo) is semidet.
+
      % map_foldl(P, CA, CB, !Acc):
      %
      % This predicate calls P on each element of the input cord, working
@@ -327,6 +367,13 @@ is_empty(empty_cord).

  singleton(X) = nonempty_cord(unit_node(X)).

+is_singleton(C, X) :-
+    (
+        C = nonempty_cord(unit_node(X))
+    ;
+        C = nonempty_cord(list_node(X, []))
+    ).
+
  %---------------------------------------------------------------------------%

  from_list(Xs) = C :-
@@ -932,6 +979,78 @@ foldr_node_pred(P, C, Cs, !Acc) :-
  foldr_node_pred(P, branch_node(A, B), Cs, !Acc) :-
      foldr_node_pred(P, B, [A | Cs], !Acc).

+foldr2(_P, empty_cord, !Acc1, !Acc2).
+foldr2(P, nonempty_cord(N), !Acc1, !Acc2) :-
+    foldr2_node(P, N, [], !Acc1, !Acc2).
+
+:- pred foldr2_node(pred(T, A, A, B, B), cord_node(T), list(cord_node(T)),
+    A, A, B, B).
+:- mode foldr2_node(in(pred(in, in, out, in, out) is det), in, in,
+    in, out, in, out) is det.
+:- mode foldr2_node(in(pred(in, in, out, mdi, muo) is det), in, in,
+    in, out, mdi, muo) is det.
+:- mode foldr2_node(in(pred(in, in, out, di, uo) is det), in, in,
+    in, out, di, uo) is det.
+:- mode foldr2_node(in(pred(in, in, out, in, out) is semidet), in, in,
+    in, out, in, out) is semidet.
+:- mode foldr2_node(in(pred(in, in, out, mdi, muo) is semidet), in, in,
+    in, out, mdi, muo) is semidet.
+:- mode foldr2_node(in(pred(in, in, out, di, uo) is semidet), in, in,
+    in, out, di, uo) is semidet.
+
+foldr2_node(P, C, Cs, !Acc1, !Acc2) :-
+    (
+        C = unit_node(X),
+        P(X, !Acc1, !Acc2)
+    ;
+        C = list_node(H, T),
+        list.foldr2(P, [H | T], !Acc1, !Acc2)
+    ),
+    (
+        Cs = []
+    ;
+        Cs = [Y | Ys],
+        foldr2_node(P, Y, Ys, !Acc1, !Acc2)
+    ).
+foldr2_node(P, branch_node(A, B), Cs, !Acc1, !Acc2) :-
+    foldr2_node(P, B, [A | Cs], !Acc1, !Acc2).
+
+foldr3(_P, empty_cord, !Acc1, !Acc2, !Acc3).
+foldr3(P, nonempty_cord(N), !Acc1, !Acc2, !Acc3) :-
+    foldr3_node(P, N, [], !Acc1, !Acc2, !Acc3).
+
+:- pred foldr3_node(pred(T, A, A, B, B, C, C), cord_node(T),
+    list(cord_node(T)), A, A, B, B, C, C).
+:- mode foldr3_node(in(pred(in, in, out, in, out, in, out) is det), in,
+    in, in, out, in, out, in, out) is det.
+:- mode foldr3_node(in(pred(in, in, out, in, out, mdi, muo) is det), in,
+    in, in, out, in, out, mdi, muo) is det.
+:- mode foldr3_node(in(pred(in, in, out, in, out, di, uo) is det), in,
+    in, in, out, in, out, di, uo) is det.
+:- mode foldr3_node(in(pred(in, in, out, in, out, in, out) is semidet), in,
+    in, in, out, in, out, in, out) is semidet.
+:- mode foldr3_node(in(pred(in, in, out, in, out, mdi, muo) is semidet), in,
+    in, in, out, in, out, mdi, muo) is semidet.
+:- mode foldr3_node(in(pred(in, in, out, in, out, di, uo) is semidet), in,
+    in, in, out, in, out, di, uo) is semidet.
+
+foldr3_node(P, C, Cs, !Acc1, !Acc2, !Acc3) :-
+    (
+        C = unit_node(X),
+        P(X, !Acc1, !Acc2, !Acc3)
+    ;
+        C = list_node(H, T),
+        list.foldr3(P, [H | T], !Acc1, !Acc2, !Acc3)
+    ),
+    (
+        Cs = []
+    ;
+        Cs = [Y | Ys],
+        foldr3_node(P, Y, Ys, !Acc1, !Acc2, !Acc3)
+    ).
+foldr3_node(P, branch_node(A, B), Cs, !Acc1, !Acc2, !Acc3) :-
+    foldr3_node(P, B, [A | Cs], !Acc1, !Acc2, !Acc3).
+
  %---------------------------------------------------------------------------%

  map_foldl(_P, empty_cord, empty_cord, !A).
diff --git a/tests/hard_coded/Mmakefile b/tests/hard_coded/Mmakefile
index a67ae2f..89e2a60 100644
--- a/tests/hard_coded/Mmakefile
+++ b/tests/hard_coded/Mmakefile
@@ -430,6 +430,7 @@ ORDINARY_PROGS = \
  	test_char_digits \
  	test_cord \
  	test_cord2 \
+	test_cord3 \
  	test_imported_no_tag \
  	test_infinity \
  	test_int_hash \
diff --git a/tests/hard_coded/test_cord3.exp b/tests/hard_coded/test_cord3.exp
index e69de29..26cb216 100644
--- a/tests/hard_coded/test_cord3.exp
+++ b/tests/hard_coded/test_cord3.exp
@@ -0,0 +1,11 @@
+Empty is empty.
+Singleton1 is not empty.
+Singleton2 is not empty.
+NonSingleton1 is not empty.
+NonSingleton2 is not empty.
+
+Empty is not a singleton.
+Singleton1 is a singleton with element 1.
+Singleton2 is a singleton with element 2.
+NonSingleton1 is not a singleton.
+NonSingleton2 is not a singleton.
diff --git a/tests/hard_coded/test_cord3.m b/tests/hard_coded/test_cord3.m
index e69de29..c35a448 100644
--- a/tests/hard_coded/test_cord3.m
+++ b/tests/hard_coded/test_cord3.m
@@ -0,0 +1,63 @@
+%---------------------------------------------------------------------------%
+% vim: ts=4 sw=4 et ft=mercury
+%---------------------------------------------------------------------------%
+
+:- module test_cord3.
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+%---------------------------------------------------------------------------%
+%---------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module cord.
+:- import_module list.
+:- import_module pair.
+:- import_module string.
+
+%---------------------------------------------------------------------------%
+
+main(!IO) :-
+    list.foldl(test_is_empty, test_cords, !IO),
+    io.nl(!IO),
+    list.foldl(test_is_singleton, test_cords, !IO).
+
+%---------------------------------------------------------------------------%
+
+:- pred test_is_empty(pair(string, cord(int))::in, io::di, io::uo) is det.
+
+test_is_empty(Name - Cord, !IO) :-
+    Result = ( if cord.is_empty(Cord) then "empty" else "not empty" ),
+    io.format("%s is %s.\n", [s(Name), s(Result)], !IO).
+
+%---------------------------------------------------------------------------%
+
+:- pred test_is_singleton(pair(string, cord(int))::in, io::di, io::uo) is det.
+
+test_is_singleton(Name - Cord, !IO) :-
+    ( if cord.is_singleton(Cord, Result) then
+        io.format("%s is a singleton with element %d.\n",
+            [s(Name), i(Result)], !IO)
+    else
+        io.format("%s is not a singleton.\n", [s(Name)], !IO)
+    ).
+
+%---------------------------------------------------------------------------%
+
+:- func test_cords = list(pair(string, cord(int))).
+
+test_cords = [
+    "Empty" - cord.empty,
+    "Singleton1" - cord.singleton(1),
+    "Singleton2" - cord.from_list([2]),
+    "NonSingleton1" - cord.from_list([3, 4]),
+    "NonSingleton2" - (cord.singleton(5) ++ cord.singleton(6))
+].
+
+%---------------------------------------------------------------------------%
+:- end_module test_cord3.
+%---------------------------------------------------------------------------%