[m-rev.] for review: library improvements
Zoltan Somogyi
zs at csse.unimelb.edu.au
Fri Aug 6 09:43:07 AEST 2010
For review by anyone. Since the diff to cord.m is effectively a total rewrite,
I am attaching the new version of the implementation section that file,
and you probably want to review that instead of the diff.
(There is only the diff for list.m.)
Zoltan.
Library improvements.
library/list.m:
Replace some semidet code with det code. This leads to a speedup
of about 1.2% on tools/speedtest -l.
library/cord.m:
Replace the type representing cords. The old type had many different
ways of representing the empty list, and had to rely on a convention
to avoid all but one of them. By design, the new type has only one
representation of the empty list.
The basic idea is to represent the empty/nonempty distinction at the
top level, and to use another type to represent nonempty cords.
This other type is like the ord cord type, but without nil.
The existence of two levels rather than one in the representation
can be expected to lead to a slight constant slowdown, but on the other
hand, the existence of only three rather than four function symbols
in the type that all the recursive code handles can be expected to lead
to a slight linear-size speedup. On tools/speedtest -l, the result
is a very slight speedup, though it is so small that it is in the
noise.
:- implementation.
:- import_module int.
:- import_module require.
:- type cord(T)
---> empty_cord
; nonempty_cord(cord_node(T)).
:- type cord_node(T)
---> unit_node(T)
; list_node(T, list(T))
; branch_node(cord_node(T), cord_node(T)).
%-----------------------------------------------------------------------------%
empty = empty_cord.
%-----------------------------------------------------------------------------%
is_empty(empty_cord).
%-----------------------------------------------------------------------------%
singleton(X) = nonempty_cord(unit_node(X)).
%-----------------------------------------------------------------------------%
from_list(Xs) = C :-
(
Xs = [],
C = empty_cord
;
Xs = [H | T],
C = nonempty_cord(list_node(H, T))
).
%-----------------------------------------------------------------------------%
list(empty_cord) = [].
list(nonempty_cord(N)) = list_2(N, []).
% list_2(N, L0) = L:
%
% L is the list of items in N appended in front of L0.
%
:- func list_2(cord_node(T), list(T)) = list(T).
list_2(unit_node(X), L0) = [X | L0].
list_2(list_node(H, T), L0) = [H | T ++ L0].
list_2(branch_node(A, B), L0) = list_2(A, list_2(B, L0)).
rev_list(empty_cord) = [].
rev_list(nonempty_cord(N)) = rev_list_2(N, []).
% rev_list_2(N, L0) = L:
%
% L is the reverse list of items in N appended in front of L0.
%
:- func rev_list_2(cord_node(T), list(T)) = list(T).
rev_list_2(unit_node(X), L0) = [X | L0].
rev_list_2(list_node(H, T), L0) = list_reverse_2(T, [H | L0]).
rev_list_2(branch_node(A, B), L0) = rev_list_2(B, list_2(A, L0)).
% list_reverse_2(A, L0) = L:
%
% L is the reverse list of items in A appended in front of L0.
%
:- func list_reverse_2(list(A), list(A)) = list(A).
list_reverse_2([], L) = L.
list_reverse_2([X | Xs], L0) =
list_reverse_2(Xs, [X | L0]).
%-----------------------------------------------------------------------------%
cons(X, C) = XC :-
(
C = empty_cord,
XC = nonempty_cord(unit_node(X))
;
C = nonempty_cord(N),
XC = nonempty_cord(branch_node(unit_node(X), N))
).
%-----------------------------------------------------------------------------%
snoc(C, X) = CX :-
(
C = empty_cord,
CX = nonempty_cord(unit_node(X))
;
C = nonempty_cord(N),
CX = nonempty_cord(branch_node(N, unit_node(X)))
).
%-----------------------------------------------------------------------------%
A ++ B = C :-
(
A = empty_cord,
C = B
;
A = nonempty_cord(_),
B = empty_cord,
C = A
;
A = nonempty_cord(AN),
B = nonempty_cord(BN),
C = nonempty_cord(branch_node(AN, BN))
).
%-----------------------------------------------------------------------------%
cord_list_to_cord([]) = empty_cord.
cord_list_to_cord([HeadCord | TailCords]) =
HeadCord ++ cord_list_to_cord(TailCords).
cord_list_to_list([]) = [].
cord_list_to_list([HeadCord | TailCords]) = List :-
TailList = cord_list_to_list(TailCords),
(
HeadCord = empty_cord,
List = TailList
;
HeadCord = nonempty_cord(HeadNode),
List = list_2(HeadNode, TailList)
).
%-----------------------------------------------------------------------------%
head_tail(nonempty_cord(N), H, T) :-
head_tail_node(N, H, T).
:- pred head_tail_node(cord_node(T)::in, T::out, cord(T)::out) is det.
head_tail_node(Node, Head, Tail) :-
(
Node = unit_node(Head),
Tail = empty_cord
;
Node = list_node(H, T),
Head = H,
(
T = [],
Tail = empty_cord
;
T = [TH | TT],
Tail = nonempty_cord(list_node(TH, TT))
)
;
Node = branch_node(A0, B),
head_tail_node(A0, Head, AC),
(
AC = empty_cord,
Tail = nonempty_cord(B)
;
AC = nonempty_cord(A),
Tail = nonempty_cord(branch_node(A, B))
)
).
%-----------------------------------------------------------------------------%
split_last(nonempty_cord(N), AllButLast, Last) :-
split_last_node(N, AllButLast, Last).
:- pred split_last_node(cord_node(T)::in, cord(T)::out, T::out) is det.
split_last_node(Node, AllButLast, Last) :-
(
Node = unit_node(Last),
AllButLast = empty_cord
;
Node = list_node(H, T),
split_list_last(H, T, AllButLastList, Last),
(
AllButLastList = [],
AllButLast = empty_cord
;
AllButLastList = [AllButLastHead | AllButLastTail],
AllButLast = nonempty_cord(
list_node(AllButLastHead, AllButLastTail))
)
;
Node = branch_node(A, B0),
split_last_node(B0, B, Last),
AllButLast = nonempty_cord(A) ++ B
).
:- pred split_list_last(T::in, list(T)::in, list(T)::out, T::out) is det.
split_list_last(Prev, [], [], Prev).
split_list_last(Prev, [H | T], AllButLast, Last) :-
split_list_last(H, T, AllButLast0, Last),
AllButLast = [Prev | AllButLast0].
%-----------------------------------------------------------------------------%
get_first(nonempty_cord(N), Head) :-
get_first_node(N, Head).
:- pred get_first_node(cord_node(T)::in, T::out) is det.
get_first_node(Node, Head) :-
(
Node = unit_node(Head)
;
Node = list_node(Head, _)
;
Node = branch_node(A, _),
get_first_node(A, Head)
).
%-----------------------------------------------------------------------------%
get_last(nonempty_cord(N), Last) :-
get_last_node(N, Last).
:- pred get_last_node(cord_node(T)::in, T::out) is det.
get_last_node(Node, Last) :-
(
Node = unit_node(Last)
;
Node = list_node(Head, Tail),
(
Tail = [],
Last = Head
;
Tail = [_ | _],
list.last_det(Tail, Last)
)
;
Node = branch_node(_, B),
get_last_node(B, Last)
).
%-----------------------------------------------------------------------------%
length(C) = foldl(func(_, N) = N + 1, C, 0).
%-----------------------------------------------------------------------------%
member(X, nonempty_cord(N)) :-
member_node(X, N).
:- pred member_node(T::out, cord_node(T)::in) is nondet.
member_node(X, Node) :-
(
Node = unit_node(X)
;
Node = list_node(H, T),
(
X = H
;
member(X, T)
)
;
Node = branch_node(A, B),
(
member_node(X, A)
;
member_node(X, B)
)
).
%-----------------------------------------------------------------------------%
map(_, empty_cord) = empty_cord.
map(F, nonempty_cord(N)) = nonempty_cord(map_node(F, N)).
:- func map_node(func(T) = U, cord_node(T)) = cord_node(U).
map_node(F, Node) = PNode :-
(
Node = unit_node(X),
PNode = unit_node(F(X))
;
Node = list_node(H, T),
PNode = list_node(F(H), list.map(F, T))
;
Node = branch_node(A, B),
PNode = branch_node(map_node(F, A), map_node(F, B))
).
map_pred(_, empty_cord, empty_cord).
map_pred(P, nonempty_cord(N), nonempty_cord(PN)) :-
map_pred_node(P, N, PN).
:- pred map_pred_node(pred(T, U)::in(pred(in, out) is det),
cord_node(T)::in, cord_node(U)::out) is det.
map_pred_node(P, Node, PNode) :-
(
Node = unit_node(X),
P(X, PX),
PNode = unit_node(PX)
;
Node = list_node(H, T),
P(H, PH),
list.map(P, T, PT),
PNode = list_node(PH, PT)
;
Node = branch_node(A, B),
cord.map_pred_node(P, A, PA),
cord.map_pred_node(P, B, PB),
PNode = branch_node(PA, PB)
).
%-----------------------------------------------------------------------------%
filter(_, empty_cord, empty_cord).
filter(P, nonempty_cord(N), Trues) :-
filter_node(P, N, Trues).
:- pred filter_node(pred(T)::in(pred(in) is semidet),
cord_node(T)::in, cord(T)::out) is det.
filter_node(P, Node, Trues) :-
(
Node = unit_node(X),
( P(X) ->
Trues = nonempty_cord(unit_node(X))
;
Trues = empty_cord
)
;
Node = list_node(H, T),
list.filter(P, [H | T], TrueList),
(
TrueList = [],
Trues = empty_cord
;
TrueList = [TH | TT],
Trues = nonempty_cord(list_node(TH, TT))
)
;
Node = branch_node(A, B),
filter_node(P, A, CATrues),
filter_node(P, B, CBTrues),
Trues = CATrues ++ CBTrues
).
%-----------------------------------------------------------------------------%
filter(_, empty_cord, empty_cord, empty_cord).
filter(P, nonempty_cord(N), Trues, Falses) :-
filter_node(P, N, Trues, Falses).
:- pred filter_node(pred(T)::in(pred(in) is semidet),
cord_node(T)::in, cord(T)::out, cord(T)::out) is det.
filter_node(P, Node, Trues, Falses) :-
(
Node = unit_node(X),
( P(X) ->
Trues = nonempty_cord(unit_node(X)),
Falses = empty_cord
;
Trues = empty_cord,
Falses = nonempty_cord(unit_node(X))
)
;
Node = list_node(H, T),
list.filter(P, [H | T], TrueList, FalseList),
(
TrueList = [],
Trues = empty_cord
;
TrueList = [TH | TT],
Trues = nonempty_cord(list_node(TH, TT))
),
(
FalseList = [],
Falses = empty_cord
;
FalseList = [FH | FT],
Falses = nonempty_cord(list_node(FH, FT))
)
;
Node = branch_node(A, B),
filter_node(P, A, CATrues, CAFalses),
filter_node(P, B, CBTrues, CBFalses),
Trues = CATrues ++ CBTrues,
Falses = CAFalses ++ CBFalses
).
%-----------------------------------------------------------------------------%
foldl(_, empty_cord, Acc) = Acc.
foldl(F, nonempty_cord(N), Acc) = foldl_node(F, N, Acc).
:- func foldl_node(func(T, U) = U, cord_node(T), U) = U.
foldl_node(F, unit_node(X), Acc) = F(X, Acc).
foldl_node(F, list_node(H, T), Acc) = list.foldl(F, [H | T], Acc).
foldl_node(F, branch_node(A, B), Acc) =
foldl_node(F, B, foldl_node(F, A, Acc)).
foldl_pred(_P, empty_cord, !Acc).
foldl_pred(P, nonempty_cord(N), !Acc) :-
foldl_node_pred(P, N, !Acc).
:- pred foldl_node_pred(pred(T, U, U), cord_node(T), U, U).
:- mode foldl_node_pred(in(pred(in, in, out) is det), in, in, out) is det.
:- mode foldl_node_pred(in(pred(in, di, uo) is det), in, di, uo) is det.
foldl_node_pred(P, unit_node(X), !Acc) :-
P(X, !Acc).
foldl_node_pred(P, list_node(H, T), !Acc) :-
list.foldl(P, [H | T], !Acc).
foldl_node_pred(P, branch_node(A, B), !Acc) :-
foldl_node_pred(P, A, !Acc),
foldl_node_pred(P, B, !Acc).
%-----------------------------------------------------------------------------%
foldr(_, empty_cord, Acc) = Acc.
foldr(F, nonempty_cord(N), Acc) = foldr_node(F, N, Acc).
:- func foldr_node(func(T, U) = U, cord_node(T), U) = U.
foldr_node(F, unit_node(X), Acc) = F(X, Acc).
foldr_node(F, list_node(H, T), Acc) = list.foldr(F, [H | T], Acc).
foldr_node(F, branch_node(A, B), Acc) =
foldr_node(F, A, foldr_node(F, B, Acc)).
foldr_pred(_P, empty_cord, !Acc).
foldr_pred(P, nonempty_cord(N), !Acc) :-
foldr_node_pred(P, N, !Acc).
:- pred foldr_node_pred(pred(T, U, U)::in(pred(in, in, out) is det),
cord_node(T)::in, U::in, U::out) is det.
foldr_node_pred(P, unit_node(X), !Acc) :-
P(X, !Acc).
foldr_node_pred(P, list_node(H, T), !Acc) :-
list.foldr(P, [H | T], !Acc).
foldr_node_pred(P, branch_node(A, B), !Acc) :-
foldr_node_pred(P, B, !Acc),
foldr_node_pred(P, A, !Acc).
%-----------------------------------------------------------------------------%
map_foldl(_P, empty_cord, empty_cord, !A).
map_foldl(P, nonempty_cord(NX), nonempty_cord(NY), !A) :-
map_foldl_node(P, NX, NY, !A).
:- pred map_foldl_node(pred(A, B, C, C)::in(pred(in, out, in, out) is det),
cord_node(A)::in, cord_node(B)::out, C::in, C::out) is det.
map_foldl_node(P, unit_node(X), unit_node(Y), !A) :-
P(X, Y, !A).
map_foldl_node(P, list_node(XH, XT), list_node(YH, YT), !A) :-
P(XH, YH, !A),
list.map_foldl(P, XT, YT, !A).
map_foldl_node(P, branch_node(XA, XB), branch_node(YA, YB), !A) :-
map_foldl_node(P, XA, YA, !A),
map_foldl_node(P, XB, YB, !A).
%-----------------------------------------------------------------------------%
map_foldl2(_P, empty_cord, empty_cord, !A, !B).
map_foldl2(P, nonempty_cord(NX), nonempty_cord(NY), !A, !B) :-
map_foldl2_node(P, NX, NY, !A, !B).
:- pred map_foldl2_node(pred(A, B, C, C, D, D)::
in(pred(in, out, in, out, in, out) is det),
cord_node(A)::in, cord_node(B)::out, C::in, C::out, D::in, D::out) is det.
map_foldl2_node(P, unit_node(X), unit_node(Y), !A, !B) :-
P(X, Y, !A, !B).
map_foldl2_node(P, list_node(XH, XT), list_node(YH, YT), !A, !B) :-
P(XH, YH, !A, !B),
list.map_foldl2(P, XT, YT, !A, !B).
map_foldl2_node(P, branch_node(XA, XB), branch_node(YA, YB), !A, !B) :-
map_foldl2_node(P, XA, YA, !A, !B),
map_foldl2_node(P, XB, YB, !A, !B).
%-----------------------------------------------------------------------------%
map_foldl3(_P, empty_cord, empty_cord, !A, !B, !C).
map_foldl3(P, nonempty_cord(NX), nonempty_cord(NY), !A, !B, !C) :-
map_foldl3_node(P, NX, NY, !A, !B, !C).
:- pred map_foldl3_node(pred(A, B, C, C, D, D, E, E)::
in(pred(in, out, in, out, in, out, in, out) is det),
cord_node(A)::in, cord_node(B)::out, C::in, C::out, D::in, D::out,
E::in, E::out) is det.
map_foldl3_node(P, unit_node(X), unit_node(Y), !A, !B, !C) :-
P(X, Y, !A, !B, !C).
map_foldl3_node(P, list_node(XH, XT), list_node(YH, YT), !A, !B, !C) :-
P(XH, YH, !A, !B, !C),
list.map_foldl3(P, XT, YT, !A, !B, !C).
map_foldl3_node(P, branch_node(XA, XB), branch_node(YA, YB), !A, !B, !C) :-
map_foldl3_node(P, XA, YA, !A, !B, !C),
map_foldl3_node(P, XB, YB, !A, !B, !C).
%-----------------------------------------------------------------------------%
equal(CA, CB) :-
% A more efficient algorithm would also be *much* more complex.
list(CA) = list(CB).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
cvs diff: Diffing .
cvs diff: Diffing analysis
cvs diff: Diffing bindist
cvs diff: Diffing boehm_gc
cvs diff: Diffing boehm_gc/Mac_files
cvs diff: Diffing boehm_gc/cord
cvs diff: Diffing boehm_gc/cord/private
cvs diff: Diffing boehm_gc/doc
cvs diff: Diffing boehm_gc/extra
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/extra
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing boehm_gc/libatomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops/doc
cvs diff: Diffing boehm_gc/libatomic_ops/src
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/armcc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/gcc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/hpc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/ibmc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/icc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/msftc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/sunc
cvs diff: Diffing boehm_gc/libatomic_ops/tests
cvs diff: Diffing boehm_gc/libatomic_ops-1.2
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/doc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/tests
cvs diff: Diffing boehm_gc/m4
cvs diff: Diffing boehm_gc/tests
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
cvs diff: Diffing compiler/notes
cvs diff: Diffing deep_profiler
cvs diff: Diffing deep_profiler/notes
cvs diff: Diffing doc
cvs diff: Diffing extras
cvs diff: Diffing extras/base64
cvs diff: Diffing extras/cgi
cvs diff: Diffing extras/complex_numbers
cvs diff: Diffing extras/complex_numbers/samples
cvs diff: Diffing extras/complex_numbers/tests
cvs diff: Diffing extras/concurrency
cvs diff: Diffing extras/curs
cvs diff: Diffing extras/curs/samples
cvs diff: Diffing extras/curses
cvs diff: Diffing extras/curses/sample
cvs diff: Diffing extras/dynamic_linking
cvs diff: Diffing extras/error
cvs diff: Diffing extras/fixed
cvs diff: Diffing extras/gator
cvs diff: Diffing extras/gator/generations
cvs diff: Diffing extras/gator/generations/1
cvs diff: Diffing extras/graphics
cvs diff: Diffing extras/graphics/easyx
cvs diff: Diffing extras/graphics/easyx/samples
cvs diff: Diffing extras/graphics/mercury_allegro
cvs diff: Diffing extras/graphics/mercury_allegro/examples
cvs diff: Diffing extras/graphics/mercury_allegro/samples
cvs diff: Diffing extras/graphics/mercury_allegro/samples/demo
cvs diff: Diffing extras/graphics/mercury_allegro/samples/mandel
cvs diff: Diffing extras/graphics/mercury_allegro/samples/pendulum2
cvs diff: Diffing extras/graphics/mercury_allegro/samples/speed
cvs diff: Diffing extras/graphics/mercury_glut
cvs diff: Diffing extras/graphics/mercury_opengl
cvs diff: Diffing extras/graphics/mercury_tcltk
cvs diff: Diffing extras/graphics/samples
cvs diff: Diffing extras/graphics/samples/calc
cvs diff: Diffing extras/graphics/samples/gears
cvs diff: Diffing extras/graphics/samples/maze
cvs diff: Diffing extras/graphics/samples/pent
cvs diff: Diffing extras/lazy_evaluation
cvs diff: Diffing extras/lex
cvs diff: Diffing extras/lex/samples
cvs diff: Diffing extras/lex/tests
cvs diff: Diffing extras/log4m
cvs diff: Diffing extras/logged_output
cvs diff: Diffing extras/moose
cvs diff: Diffing extras/moose/samples
cvs diff: Diffing extras/moose/tests
cvs diff: Diffing extras/mopenssl
cvs diff: Diffing extras/morphine
cvs diff: Diffing extras/morphine/non-regression-tests
cvs diff: Diffing extras/morphine/scripts
cvs diff: Diffing extras/morphine/source
cvs diff: Diffing extras/net
cvs diff: Diffing extras/odbc
cvs diff: Diffing extras/posix
cvs diff: Diffing extras/posix/samples
cvs diff: Diffing extras/quickcheck
cvs diff: Diffing extras/quickcheck/tutes
cvs diff: Diffing extras/references
cvs diff: Diffing extras/references/samples
cvs diff: Diffing extras/references/tests
cvs diff: Diffing extras/solver_types
cvs diff: Diffing extras/solver_types/library
cvs diff: Diffing extras/trailed_update
cvs diff: Diffing extras/trailed_update/samples
cvs diff: Diffing extras/trailed_update/tests
cvs diff: Diffing extras/windows_installer_generator
cvs diff: Diffing extras/windows_installer_generator/sample
cvs diff: Diffing extras/windows_installer_generator/sample/images
cvs diff: Diffing extras/xml
cvs diff: Diffing extras/xml/samples
cvs diff: Diffing extras/xml_stylesheets
cvs diff: Diffing java
cvs diff: Diffing java/runtime
cvs diff: Diffing library
Index: library/cord.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/cord.m,v
retrieving revision 1.15
diff -u -b -r1.15 cord.m
--- library/cord.m 30 Jan 2009 03:51:44 -0000 1.15
+++ library/cord.m 5 Aug 2010 09:39:35 -0000
@@ -198,70 +198,65 @@
:- import_module int.
:- import_module require.
- % We impose the following invariants to ensure we have a unique
- % representation for the empty cord (this makes the implementation
- % simpler.)
- %
- % all [C] not C = leaves([])
- % all [C] not C = branch(nil, _)
- % all [C] not C = branch(_, nil)
- %
:- type cord(T)
- ---> nil
- ; leaf(T)
- ; leaves(list(T))
- ; branch(cord(T), cord(T)).
+ ---> empty_cord
+ ; nonempty_cord(cord_node(T)).
+
+:- type cord_node(T)
+ ---> unit_node(T)
+ ; list_node(T, list(T))
+ ; branch_node(cord_node(T), cord_node(T)).
%-----------------------------------------------------------------------------%
-empty = nil.
+empty = empty_cord.
%-----------------------------------------------------------------------------%
-is_empty(nil).
+is_empty(empty_cord).
%-----------------------------------------------------------------------------%
-singleton(X) = leaf(X).
+singleton(X) = nonempty_cord(unit_node(X)).
%-----------------------------------------------------------------------------%
from_list(Xs) = C :-
(
Xs = [],
- C = nil
+ C = empty_cord
;
- Xs = [_ | _],
- C = leaves(Xs)
+ Xs = [H | T],
+ C = nonempty_cord(list_node(H, T))
).
%-----------------------------------------------------------------------------%
-list(C) = list_2(C, []).
+list(empty_cord) = [].
+list(nonempty_cord(N)) = list_2(N, []).
- % list_2(C, L0) = L:
+ % list_2(N, L0) = L:
%
- % L is the list of items in C appended in front of L0.
+ % L is the list of items in N appended in front of L0.
%
-:- func list_2(cord(T), list(T)) = list(T).
+:- func list_2(cord_node(T), list(T)) = list(T).
-list_2(nil, Xs) = Xs.
-list_2(leaf(Y), Xs) = [Y | Xs].
-list_2(leaves(Ys), Xs) = Ys ++ Xs.
-list_2(branch(CA, CB), Xs) = list_2(CA, list_2(CB, Xs)).
+list_2(unit_node(X), L0) = [X | L0].
+list_2(list_node(H, T), L0) = [H | T ++ L0].
+list_2(branch_node(A, B), L0) = list_2(A, list_2(B, L0)).
-rev_list(C) = rev_list_2(C, []).
+rev_list(empty_cord) = [].
+rev_list(nonempty_cord(N)) = rev_list_2(N, []).
- % rev_list_2(C, L0) = L:
+ % rev_list_2(N, L0) = L:
%
- % L is the reverse list of items in C appended in front of L0.
+ % L is the reverse list of items in N appended in front of L0.
%
-:- func rev_list_2(cord(T), list(T)) = list(T).
+:- func rev_list_2(cord_node(T), list(T)) = list(T).
-rev_list_2(nil, Xs) = Xs.
-rev_list_2(leaf(Y), Xs) = [Y | Xs].
-rev_list_2(leaves(Ys), Xs) = list_reverse_2(Ys, Xs).
-rev_list_2(branch(CA, CB), Xs) = rev_list_2(CB, list_2(CA, Xs)).
+rev_list_2(unit_node(X), L0) = [X | L0].
+rev_list_2(list_node(H, T), L0) = list_reverse_2(T, [H | L0]).
+rev_list_2(branch_node(A, B), L0) = rev_list_2(B, list_2(A, L0)).
% list_reverse_2(A, L0) = L:
%
@@ -277,129 +272,165 @@
cons(X, C) = XC :-
(
- C = nil,
- XC = leaf(X)
+ C = empty_cord,
+ XC = nonempty_cord(unit_node(X))
;
- ( C = leaf(_)
- ; C = leaves(_)
- ; C = branch(_, _)
- ),
- XC = branch(leaf(X), C)
+ C = nonempty_cord(N),
+ XC = nonempty_cord(branch_node(unit_node(X), N))
).
%-----------------------------------------------------------------------------%
snoc(C, X) = CX :-
(
- C = nil,
- CX = leaf(X)
+ C = empty_cord,
+ CX = nonempty_cord(unit_node(X))
;
- ( C = leaf(_)
- ; C = leaves(_)
- ; C = branch(_, _)
- ),
- CX = branch(C, leaf(X))
+ C = nonempty_cord(N),
+ CX = nonempty_cord(branch_node(N, unit_node(X)))
).
%-----------------------------------------------------------------------------%
-CA ++ CB = ( if CA = nil then CB
- else if CB = nil then CA
- else branch(CA, CB)
+A ++ B = C :-
+ (
+ A = empty_cord,
+ C = B
+ ;
+ A = nonempty_cord(_),
+ B = empty_cord,
+ C = A
+ ;
+ A = nonempty_cord(AN),
+ B = nonempty_cord(BN),
+ C = nonempty_cord(branch_node(AN, BN))
).
%-----------------------------------------------------------------------------%
-cord_list_to_cord([]) = nil.
+cord_list_to_cord([]) = empty_cord.
cord_list_to_cord([HeadCord | TailCords]) =
HeadCord ++ cord_list_to_cord(TailCords).
cord_list_to_list([]) = [].
-cord_list_to_list([HeadCord | TailCords]) =
- list(HeadCord) ++ cord_list_to_list(TailCords).
-
-%-----------------------------------------------------------------------------%
-
-head_tail(leaf(X), X, nil).
-head_tail(leaves([X | Xs]), X, C ) :-
+cord_list_to_list([HeadCord | TailCords]) = List :-
+ TailList = cord_list_to_list(TailCords),
(
- Xs = [],
- C = nil
+ HeadCord = empty_cord,
+ List = TailList
;
- Xs = [_ | _],
- C = leaves(Xs)
+ HeadCord = nonempty_cord(HeadNode),
+ List = list_2(HeadNode, TailList)
).
-head_tail(branch(CA0, CB), X, C ) :-
- head_tail(CA0, X, CA),
- C = CA ++ CB.
%-----------------------------------------------------------------------------%
-split_last(leaf(X), nil, X).
-split_last(leaves(Xs0), C, X) :-
- split_list_last(Xs0, C, X).
-split_last(branch(CA, CB0), C, X) :-
- split_last(CB0, CB, X),
- C = CA ++ CB.
+head_tail(nonempty_cord(N), H, T) :-
+ head_tail_node(N, H, T).
- % split_list_last(Xs0, C, X):
- %
- % Given a nonempty list Xs0, returns its last element as X and all the
- % elements before it as the cord C. This has a similar effect to
- %
- % list.split_last(Xs0, Xs, X),
- % C = ( if Xs = [] then nil else leaves(Xs) ).
- %
- % but while repeatedly taking the last element of a list is an O(n^2)
- % operation (since a list is a right stick), we return C as a left stick,
- % on which repeatedly taking the last element of a list is an O(n)
- % operation. This ensures O(1) amortized cost for each call to
- % split_last/3 when an entire cord is traversed with that predicate.
- %
-:- pred split_list_last(list(T)::in, cord(T)::out, T::out) is det.
+:- pred head_tail_node(cord_node(T)::in, T::out, cord(T)::out) is det.
-split_list_last([], _, _) :-
- % This violates the invariant that an empty cord is represented by nil,
- % not by leaves([]).
- error("cord.m: split_list_last finds []").
-split_list_last([H | T], InitialCord, Last) :-
+head_tail_node(Node, Head, Tail) :-
+ (
+ Node = unit_node(Head),
+ Tail = empty_cord
+ ;
+ Node = list_node(H, T),
+ Head = H,
(
T = [],
- InitialCord = nil,
- Last = H
+ Tail = empty_cord
;
T = [TH | TT],
- split_list_last_2(leaf(H), TH, TT, InitialCord, Last)
+ Tail = nonempty_cord(list_node(TH, TT))
+ )
+ ;
+ Node = branch_node(A0, B),
+ head_tail_node(A0, Head, AC),
+ (
+ AC = empty_cord,
+ Tail = nonempty_cord(B)
+ ;
+ AC = nonempty_cord(A),
+ Tail = nonempty_cord(branch_node(A, B))
+ )
).
-:- pred split_list_last_2(cord(T)::in, T::in, list(T)::in,
- cord(T)::out, T::out) is det.
+%-----------------------------------------------------------------------------%
+
+split_last(nonempty_cord(N), AllButLast, Last) :-
+ split_last_node(N, AllButLast, Last).
+
+:- pred split_last_node(cord_node(T)::in, cord(T)::out, T::out) is det.
-split_list_last_2(BeforeCord, H, T, InitialCord, Last) :-
+split_last_node(Node, AllButLast, Last) :-
(
- T = [],
- InitialCord = BeforeCord,
- Last = H
+ Node = unit_node(Last),
+ AllButLast = empty_cord
;
- T = [TH | TT],
- split_list_last_2(BeforeCord ++ leaf(H), TH, TT, InitialCord, Last)
+ Node = list_node(H, T),
+ split_list_last(H, T, AllButLastList, Last),
+ (
+ AllButLastList = [],
+ AllButLast = empty_cord
+ ;
+ AllButLastList = [AllButLastHead | AllButLastTail],
+ AllButLast = nonempty_cord(
+ list_node(AllButLastHead, AllButLastTail))
+ )
+ ;
+ Node = branch_node(A, B0),
+ split_last_node(B0, B, Last),
+ AllButLast = nonempty_cord(A) ++ B
).
+:- pred split_list_last(T::in, list(T)::in, list(T)::out, T::out) is det.
+
+split_list_last(Prev, [], [], Prev).
+split_list_last(Prev, [H | T], AllButLast, Last) :-
+ split_list_last(H, T, AllButLast0, Last),
+ AllButLast = [Prev | AllButLast0].
+
%-----------------------------------------------------------------------------%
-get_first(leaf(X), X).
-get_first(leaves(Xs), X) :-
- Xs = [X | _].
-get_first(branch(CA, _CB), X) :-
- get_first(CA, X).
+get_first(nonempty_cord(N), Head) :-
+ get_first_node(N, Head).
+
+:- pred get_first_node(cord_node(T)::in, T::out) is det.
+
+get_first_node(Node, Head) :-
+ (
+ Node = unit_node(Head)
+ ;
+ Node = list_node(Head, _)
+ ;
+ Node = branch_node(A, _),
+ get_first_node(A, Head)
+ ).
%-----------------------------------------------------------------------------%
-get_last(leaf(X), X).
-get_last(leaves(Xs), X) :-
- list.last(Xs, X).
-get_last(branch(_CA, CB), X) :-
- get_last(CB, X).
+get_last(nonempty_cord(N), Last) :-
+ get_last_node(N, Last).
+
+:- pred get_last_node(cord_node(T)::in, T::out) is det.
+
+get_last_node(Node, Last) :-
+ (
+ Node = unit_node(Last)
+ ;
+ Node = list_node(Head, Tail),
+ (
+ Tail = [],
+ Last = Head
+ ;
+ Tail = [_ | _],
+ list.last_det(Tail, Last)
+ )
+ ;
+ Node = branch_node(_, B),
+ get_last_node(B, Last)
+ ).
%-----------------------------------------------------------------------------%
@@ -407,158 +438,267 @@
%-----------------------------------------------------------------------------%
-member(X, leaf(X)).
-member(X, leaves(Xs)) :-
- member(X, Xs).
-member(X, branch(CA, _)) :-
- member(X, CA).
-member(X, branch(_, CB)) :-
- member(X, CB).
+member(X, nonempty_cord(N)) :-
+ member_node(X, N).
+
+:- pred member_node(T::out, cord_node(T)::in) is nondet.
+
+member_node(X, Node) :-
+ (
+ Node = unit_node(X)
+ ;
+ Node = list_node(H, T),
+ (
+ X = H
+ ;
+ member(X, T)
+ )
+ ;
+ Node = branch_node(A, B),
+ (
+ member_node(X, A)
+ ;
+ member_node(X, B)
+ )
+ ).
%-----------------------------------------------------------------------------%
-map(_, nil ) = nil.
-map(F, leaf(X) ) = leaf(F(X)).
-map(F, leaves(Xs) ) = leaves(map(F, Xs)).
-map(F, branch(CA, CB)) = branch(map(F, CA), map(F, CB)).
+map(_, empty_cord) = empty_cord.
+map(F, nonempty_cord(N)) = nonempty_cord(map_node(F, N)).
+
+:- func map_node(func(T) = U, cord_node(T)) = cord_node(U).
-map_pred(P, !Cord) :-
+map_node(F, Node) = PNode :-
(
- !.Cord = nil,
- !:Cord = nil
+ Node = unit_node(X),
+ PNode = unit_node(F(X))
+ ;
+ Node = list_node(H, T),
+ PNode = list_node(F(H), list.map(F, T))
;
- !.Cord = leaf(X),
+ Node = branch_node(A, B),
+ PNode = branch_node(map_node(F, A), map_node(F, B))
+ ).
+
+map_pred(_, empty_cord, empty_cord).
+map_pred(P, nonempty_cord(N), nonempty_cord(PN)) :-
+ map_pred_node(P, N, PN).
+
+:- pred map_pred_node(pred(T, U)::in(pred(in, out) is det),
+ cord_node(T)::in, cord_node(U)::out) is det.
+
+map_pred_node(P, Node, PNode) :-
+ (
+ Node = unit_node(X),
P(X, PX),
- !:Cord = leaf(PX)
+ PNode = unit_node(PX)
;
- !.Cord = leaves(Xs),
- list.map(P, Xs, PXs),
- !:Cord = leaves(PXs)
+ Node = list_node(H, T),
+ P(H, PH),
+ list.map(P, T, PT),
+ PNode = list_node(PH, PT)
;
- !.Cord = branch(CA, CB),
- cord.map_pred(P, CA, PCA),
- cord.map_pred(P, CB, PCB),
- !:Cord = branch(PCA, PCB)
+ Node = branch_node(A, B),
+ cord.map_pred_node(P, A, PA),
+ cord.map_pred_node(P, B, PB),
+ PNode = branch_node(PA, PB)
).
%-----------------------------------------------------------------------------%
-filter(_P, nil, nil).
-filter(P, leaf(X), Trues) :-
+filter(_, empty_cord, empty_cord).
+filter(P, nonempty_cord(N), Trues) :-
+ filter_node(P, N, Trues).
+
+:- pred filter_node(pred(T)::in(pred(in) is semidet),
+ cord_node(T)::in, cord(T)::out) is det.
+
+filter_node(P, Node, Trues) :-
+ (
+ Node = unit_node(X),
( P(X) ->
- Trues = leaf(X)
+ Trues = nonempty_cord(unit_node(X))
;
- Trues = nil
- ).
-filter(P, leaves(Xs), Trues) :-
- list.filter(P, Xs, TrueList),
+ Trues = empty_cord
+ )
+ ;
+ Node = list_node(H, T),
+ list.filter(P, [H | T], TrueList),
(
TrueList = [],
- Trues = nil
+ Trues = empty_cord
+ ;
+ TrueList = [TH | TT],
+ Trues = nonempty_cord(list_node(TH, TT))
+ )
;
- TrueList = [_ | _],
- Trues = leaves(TrueList)
+ Node = branch_node(A, B),
+ filter_node(P, A, CATrues),
+ filter_node(P, B, CBTrues),
+ Trues = CATrues ++ CBTrues
).
-filter(P, branch(CA, CB), Trues) :-
- filter(P, CA, CATrues),
- filter(P, CB, CBTrues),
- Trues = CATrues ++ CBTrues.
-filter(_P, nil, nil, nil).
-filter(P, leaf(X), Trues, Falses) :-
+%-----------------------------------------------------------------------------%
+
+filter(_, empty_cord, empty_cord, empty_cord).
+filter(P, nonempty_cord(N), Trues, Falses) :-
+ filter_node(P, N, Trues, Falses).
+
+:- pred filter_node(pred(T)::in(pred(in) is semidet),
+ cord_node(T)::in, cord(T)::out, cord(T)::out) is det.
+
+filter_node(P, Node, Trues, Falses) :-
+ (
+ Node = unit_node(X),
( P(X) ->
- Trues = leaf(X),
- Falses = nil
+ Trues = nonempty_cord(unit_node(X)),
+ Falses = empty_cord
;
- Trues = nil,
- Falses = leaf(X)
- ).
-filter(P, leaves(Xs), Trues, Falses) :-
- list.filter(P, Xs, TrueList, FalseList),
+ Trues = empty_cord,
+ Falses = nonempty_cord(unit_node(X))
+ )
+ ;
+ Node = list_node(H, T),
+ list.filter(P, [H | T], TrueList, FalseList),
(
TrueList = [],
- Trues = nil
+ Trues = empty_cord
;
- TrueList = [_ | _],
- Trues = leaves(TrueList)
+ TrueList = [TH | TT],
+ Trues = nonempty_cord(list_node(TH, TT))
),
(
FalseList = [],
- Falses = nil
+ Falses = empty_cord
;
- FalseList = [_ | _],
- Falses = leaves(FalseList)
- ).
-filter(P, branch(CA, CB), Trues, Falses) :-
- filter(P, CA, CATrues, CAFalses),
- filter(P, CB, CBTrues, CBFalses),
+ FalseList = [FH | FT],
+ Falses = nonempty_cord(list_node(FH, FT))
+ )
+ ;
+ Node = branch_node(A, B),
+ filter_node(P, A, CATrues, CAFalses),
+ filter_node(P, B, CBTrues, CBFalses),
Trues = CATrues ++ CBTrues,
- Falses = CAFalses ++ CBFalses.
+ Falses = CAFalses ++ CBFalses
+ ).
%-----------------------------------------------------------------------------%
-foldl(_, nil, A) = A.
-foldl(F, leaf(X), A) = F(X, A).
-foldl(F, leaves(Xs), A) = foldl(F, Xs, A).
-foldl(F, branch(CA, CB), A) = foldl(F, CB, foldl(F, CA, A)).
+foldl(_, empty_cord, Acc) = Acc.
+foldl(F, nonempty_cord(N), Acc) = foldl_node(F, N, Acc).
+
+:- func foldl_node(func(T, U) = U, cord_node(T), U) = U.
-foldl_pred(_P, nil, !A).
-foldl_pred(P, leaf(X), !A) :-
- P(X, !A).
-foldl_pred(P, leaves(Xs), !A) :-
- list.foldl(P, Xs, !A).
-foldl_pred(P, branch(XA, XB), !A) :-
- foldl_pred(P, XA, !A),
- foldl_pred(P, XB, !A).
+foldl_node(F, unit_node(X), Acc) = F(X, Acc).
+foldl_node(F, list_node(H, T), Acc) = list.foldl(F, [H | T], Acc).
+foldl_node(F, branch_node(A, B), Acc) =
+ foldl_node(F, B, foldl_node(F, A, Acc)).
+
+foldl_pred(_P, empty_cord, !Acc).
+foldl_pred(P, nonempty_cord(N), !Acc) :-
+ foldl_node_pred(P, N, !Acc).
+
+:- pred foldl_node_pred(pred(T, U, U), cord_node(T), U, U).
+:- mode foldl_node_pred(in(pred(in, in, out) is det), in, in, out) is det.
+:- mode foldl_node_pred(in(pred(in, di, uo) is det), in, di, uo) is det.
+
+foldl_node_pred(P, unit_node(X), !Acc) :-
+ P(X, !Acc).
+foldl_node_pred(P, list_node(H, T), !Acc) :-
+ list.foldl(P, [H | T], !Acc).
+foldl_node_pred(P, branch_node(A, B), !Acc) :-
+ foldl_node_pred(P, A, !Acc),
+ foldl_node_pred(P, B, !Acc).
%-----------------------------------------------------------------------------%
-foldr(_, nil, A) = A.
-foldr(F, leaf(X), A) = F(X, A).
-foldr(F, leaves(Xs), A) = foldr(F, Xs, A).
-foldr(F, branch(CA, CB), A) = foldr(F, CA, foldr(F, CB, A)).
+foldr(_, empty_cord, Acc) = Acc.
+foldr(F, nonempty_cord(N), Acc) = foldr_node(F, N, Acc).
+
+:- func foldr_node(func(T, U) = U, cord_node(T), U) = U.
+
+foldr_node(F, unit_node(X), Acc) = F(X, Acc).
+foldr_node(F, list_node(H, T), Acc) = list.foldr(F, [H | T], Acc).
+foldr_node(F, branch_node(A, B), Acc) =
+ foldr_node(F, A, foldr_node(F, B, Acc)).
+
+foldr_pred(_P, empty_cord, !Acc).
+foldr_pred(P, nonempty_cord(N), !Acc) :-
+ foldr_node_pred(P, N, !Acc).
-foldr_pred(_P, nil, !A).
-foldr_pred(P, leaf(X), !A) :-
- P(X, !A).
-foldr_pred(P, leaves(Xs), !A) :-
- list.foldr(P, Xs, !A).
-foldr_pred(P, branch(XA, XB), !A) :-
- foldr_pred(P, XB, !A),
- foldr_pred(P, XA, !A).
+:- pred foldr_node_pred(pred(T, U, U)::in(pred(in, in, out) is det),
+ cord_node(T)::in, U::in, U::out) is det.
+
+foldr_node_pred(P, unit_node(X), !Acc) :-
+ P(X, !Acc).
+foldr_node_pred(P, list_node(H, T), !Acc) :-
+ list.foldr(P, [H | T], !Acc).
+foldr_node_pred(P, branch_node(A, B), !Acc) :-
+ foldr_node_pred(P, B, !Acc),
+ foldr_node_pred(P, A, !Acc).
%-----------------------------------------------------------------------------%
-map_foldl(_P, nil, nil, !A).
-map_foldl(P, leaf(X), leaf(Y), !A) :-
+map_foldl(_P, empty_cord, empty_cord, !A).
+map_foldl(P, nonempty_cord(NX), nonempty_cord(NY), !A) :-
+ map_foldl_node(P, NX, NY, !A).
+
+:- pred map_foldl_node(pred(A, B, C, C)::in(pred(in, out, in, out) is det),
+ cord_node(A)::in, cord_node(B)::out, C::in, C::out) is det.
+
+map_foldl_node(P, unit_node(X), unit_node(Y), !A) :-
P(X, Y, !A).
-map_foldl(P, leaves(Xs), leaves(Ys), !A) :-
- list.map_foldl(P, Xs, Ys, !A).
-map_foldl(P, branch(XA, XB), branch(YA, YB), !A) :-
- map_foldl(P, XA, YA, !A),
- map_foldl(P, XB, YB, !A).
+map_foldl_node(P, list_node(XH, XT), list_node(YH, YT), !A) :-
+ P(XH, YH, !A),
+ list.map_foldl(P, XT, YT, !A).
+map_foldl_node(P, branch_node(XA, XB), branch_node(YA, YB), !A) :-
+ map_foldl_node(P, XA, YA, !A),
+ map_foldl_node(P, XB, YB, !A).
+
+%-----------------------------------------------------------------------------%
+
+map_foldl2(_P, empty_cord, empty_cord, !A, !B).
+map_foldl2(P, nonempty_cord(NX), nonempty_cord(NY), !A, !B) :-
+ map_foldl2_node(P, NX, NY, !A, !B).
-map_foldl2(_P, nil, nil, !A, !B).
-map_foldl2(P, leaf(X), leaf(Y), !A, !B) :-
+:- pred map_foldl2_node(pred(A, B, C, C, D, D)::
+ in(pred(in, out, in, out, in, out) is det),
+ cord_node(A)::in, cord_node(B)::out, C::in, C::out, D::in, D::out) is det.
+
+map_foldl2_node(P, unit_node(X), unit_node(Y), !A, !B) :-
P(X, Y, !A, !B).
-map_foldl2(P, leaves(Xs), leaves(Ys), !A, !B) :-
- list.map_foldl2(P, Xs, Ys, !A, !B).
-map_foldl2(P, branch(XA, XB), branch(YA, YB), !A, !B) :-
- map_foldl2(P, XA, YA, !A, !B),
- map_foldl2(P, XB, YB, !A, !B).
+map_foldl2_node(P, list_node(XH, XT), list_node(YH, YT), !A, !B) :-
+ P(XH, YH, !A, !B),
+ list.map_foldl2(P, XT, YT, !A, !B).
+map_foldl2_node(P, branch_node(XA, XB), branch_node(YA, YB), !A, !B) :-
+ map_foldl2_node(P, XA, YA, !A, !B),
+ map_foldl2_node(P, XB, YB, !A, !B).
+
+%-----------------------------------------------------------------------------%
+
+map_foldl3(_P, empty_cord, empty_cord, !A, !B, !C).
+map_foldl3(P, nonempty_cord(NX), nonempty_cord(NY), !A, !B, !C) :-
+ map_foldl3_node(P, NX, NY, !A, !B, !C).
+
+:- pred map_foldl3_node(pred(A, B, C, C, D, D, E, E)::
+ in(pred(in, out, in, out, in, out, in, out) is det),
+ cord_node(A)::in, cord_node(B)::out, C::in, C::out, D::in, D::out,
+ E::in, E::out) is det.
-map_foldl3(_P, nil, nil, !A, !B, !C).
-map_foldl3(P, leaf(X), leaf(Y), !A, !B, !C) :-
+map_foldl3_node(P, unit_node(X), unit_node(Y), !A, !B, !C) :-
P(X, Y, !A, !B, !C).
-map_foldl3(P, leaves(Xs), leaves(Ys), !A, !B, !C) :-
- list.map_foldl3(P, Xs, Ys, !A, !B, !C).
-map_foldl3(P, branch(XA, XB), branch(YA, YB), !A, !B, !C) :-
- map_foldl3(P, XA, YA, !A, !B, !C),
- map_foldl3(P, XB, YB, !A, !B, !C).
+map_foldl3_node(P, list_node(XH, XT), list_node(YH, YT), !A, !B, !C) :-
+ P(XH, YH, !A, !B, !C),
+ list.map_foldl3(P, XT, YT, !A, !B, !C).
+map_foldl3_node(P, branch_node(XA, XB), branch_node(YA, YB), !A, !B, !C) :-
+ map_foldl3_node(P, XA, YA, !A, !B, !C),
+ map_foldl3_node(P, XB, YB, !A, !B, !C).
%-----------------------------------------------------------------------------%
equal(CA, CB) :-
+ % A more efficient algorithm would also be *much* more complex.
list(CA) = list(CB).
%-----------------------------------------------------------------------------%
Index: library/list.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/list.m,v
retrieving revision 1.191
diff -u -b -r1.191 list.m
--- library/list.m 5 Aug 2010 06:55:45 -0000 1.191
+++ library/list.m 5 Aug 2010 09:36:07 -0000
@@ -2040,11 +2040,15 @@
list.last(T, Last)
).
-list.last_det(List, Last) :-
- ( list.last(List, LastPrime) ->
- Last = LastPrime
+list.last_det([], _) :-
+ error("list.last_det: empty list").
+list.last_det([H | T], Last) :-
+ (
+ T = [],
+ Last = H
;
- error("list.last_det: empty list")
+ T = [_ | _],
+ list.last_det(T, Last)
).
list.det_last(List, Last) :-
@@ -2064,12 +2068,30 @@
AllButLast = [H | AllButLast1]
).
-list.split_last_det(List, AllButLast, Last) :-
- ( list.split_last(List, AllButLastPrime, LastPrime) ->
- AllButLast = AllButLastPrime,
- Last = LastPrime
+list.split_last_det([], _, _) :-
+ error("list.split_last_det: empty list").
+list.split_last_det([H | T], AllButLast, Last) :-
+ (
+ T = [],
+ AllButLast = [],
+ Last = H
+ ;
+ T = [TH | TT],
+ list.split_last_det_2(TH, TT, AllButLastTail, Last),
+ AllButLast = [H | AllButLastTail]
+ ).
+
+:- pred list.split_last_det_2(T::in, list(T)::in, list(T)::out, T::out) is det.
+
+list.split_last_det_2(H, T, AllButLast, Last) :-
+ (
+ T = [],
+ AllButLast = [],
+ Last = H
;
- error("list.split_last_det: empty list")
+ T = [TH | TT],
+ list.split_last_det_2(TH, TT, AllButLastTail, Last),
+ AllButLast = [H | AllButLastTail]
).
list.det_split_last(List, AllButLast, Last) :-
cvs diff: Diffing mdbcomp
cvs diff: Diffing profiler
cvs diff: Diffing robdd
cvs diff: Diffing runtime
cvs diff: Diffing runtime/GETOPT
cvs diff: Diffing runtime/machdeps
cvs diff: Diffing samples
cvs diff: Diffing samples/c_interface
cvs diff: Diffing samples/c_interface/c_calls_mercury
cvs diff: Diffing samples/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/mercury_calls_c
cvs diff: Diffing samples/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/standalone_c
cvs diff: Diffing samples/diff
cvs diff: Diffing samples/java_interface
cvs diff: Diffing samples/java_interface/java_calls_mercury
cvs diff: Diffing samples/java_interface/mercury_calls_java
cvs diff: Diffing samples/muz
cvs diff: Diffing samples/rot13
cvs diff: Diffing samples/solutions
cvs diff: Diffing samples/solver_types
cvs diff: Diffing samples/tests
cvs diff: Diffing samples/tests/c_interface
cvs diff: Diffing samples/tests/c_interface/c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/tests/c_interface/mercury_calls_c
cvs diff: Diffing samples/tests/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/tests/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/tests/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/tests/diff
cvs diff: Diffing samples/tests/muz
cvs diff: Diffing samples/tests/rot13
cvs diff: Diffing samples/tests/solutions
cvs diff: Diffing samples/tests/toplevel
cvs diff: Diffing scripts
cvs diff: Diffing slice
cvs diff: Diffing ssdb
cvs diff: Diffing tests
cvs diff: Diffing tests/analysis
cvs diff: Diffing tests/analysis/ctgc
cvs diff: Diffing tests/analysis/excp
cvs diff: Diffing tests/analysis/ext
cvs diff: Diffing tests/analysis/sharing
cvs diff: Diffing tests/analysis/table
cvs diff: Diffing tests/analysis/trail
cvs diff: Diffing tests/analysis/unused_args
cvs diff: Diffing tests/benchmarks
cvs diff: Diffing tests/debugger
cvs diff: Diffing tests/debugger/declarative
cvs diff: Diffing tests/dppd
cvs diff: Diffing tests/general
cvs diff: Diffing tests/general/accumulator
cvs diff: Diffing tests/general/string_format
cvs diff: Diffing tests/general/structure_reuse
cvs diff: Diffing tests/grade_subdirs
cvs diff: Diffing tests/hard_coded
cvs diff: Diffing tests/hard_coded/exceptions
cvs diff: Diffing tests/hard_coded/purity
cvs diff: Diffing tests/hard_coded/sub-modules
cvs diff: Diffing tests/hard_coded/typeclasses
cvs diff: Diffing tests/invalid
cvs diff: Diffing tests/invalid/purity
cvs diff: Diffing tests/misc_tests
cvs diff: Diffing tests/mmc_make
cvs diff: Diffing tests/mmc_make/lib
cvs diff: Diffing tests/par_conj
cvs diff: Diffing tests/recompilation
cvs diff: Diffing tests/stm
cvs diff: Diffing tests/stm/orig
cvs diff: Diffing tests/stm/orig/stm-compiler
cvs diff: Diffing tests/stm/orig/stm-compiler/test1
cvs diff: Diffing tests/stm/orig/stm-compiler/test10
cvs diff: Diffing tests/stm/orig/stm-compiler/test2
cvs diff: Diffing tests/stm/orig/stm-compiler/test3
cvs diff: Diffing tests/stm/orig/stm-compiler/test4
cvs diff: Diffing tests/stm/orig/stm-compiler/test5
cvs diff: Diffing tests/stm/orig/stm-compiler/test6
cvs diff: Diffing tests/stm/orig/stm-compiler/test7
cvs diff: Diffing tests/stm/orig/stm-compiler/test8
cvs diff: Diffing tests/stm/orig/stm-compiler/test9
cvs diff: Diffing tests/stm/orig/stm-compiler-par
cvs diff: Diffing tests/stm/orig/stm-compiler-par/bm1
cvs diff: Diffing tests/stm/orig/stm-compiler-par/bm2
cvs diff: Diffing tests/stm/orig/stm-compiler-par/stmqueue
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test1
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test10
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test11
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test2
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test3
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test4
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test5
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test6
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test7
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test8
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test9
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test1
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test2
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test3
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test4
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test5
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test6
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test7
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test8
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test9
cvs diff: Diffing tests/tabling
cvs diff: Diffing tests/term
cvs diff: Diffing tests/trailing
cvs diff: Diffing tests/valid
cvs diff: Diffing tests/warnings
cvs diff: Diffing tools
cvs diff: Diffing trace
cvs diff: Diffing util
cvs diff: Diffing vim
cvs diff: Diffing vim/after
cvs diff: Diffing vim/ftplugin
cvs diff: Diffing vim/syntax
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------
More information about the reviews
mailing list