[m-rev.] New library module: pile
Ralph Becket
rafe at cs.mu.OZ.AU
Thu Feb 13 11:34:42 AEDT 2003
Okay, here's a relative diff.
I've removed cons_list(Xs, C) since it's only two characters shorter
than from_list(Xs) ++ C.
I've added snoc/2 since it seems like a good idea.
I've applied s/T/C/ for cord names (the T was a hangover from the first
version where I called cord leaf_trees.)
I've redefined the semantics of most operations purely in terms of
list/1, thereby avoiding the need for auxiliary variables and
implication signs.
I've made it clear that the empty cord has a unique representation
(i.e. nil branches and leaves([]) are forbidden.)
I've made it clear that non-empty cords may represent the same
sequence, but have different representations.
I've left equal/2 as is since I don't honestly think testing these
things for equality is a good idea.
diff -u NEWS NEWS
--- NEWS 12 Feb 2003 05:57:39 -0000
+++ NEWS 13 Feb 2003 00:08:39 -0000
@@ -16,7 +16,7 @@
with `mmc --make'.
Changes to the Mercury standard library:
-* We've added a new module, cord, for collections with O(1) insertion and
+* We've added a new module, cord, for sequences with O(1) consing and
concatenation.
Portability improvements:
@@ -62,8 +62,10 @@
Changes to the Mercury standard library:
-* We've added a new module, cord, for collections with O(1) insertion and
- concatenation.
+* We've added a new module, cord, for sequences with O(1) consing and
+ concatenation. A cord is essentially a tree structure with data stored
+ in the leaf nodes. Joining two cords together to construct a new cord
+ is therefore an O(1) operation.
* We've added a new library module, `array2d'.
diff -u library/cord.m library/cord.m
--- library/cord.m 12 Feb 2003 05:38:34 -0000
+++ library/cord.m 13 Feb 2003 00:30:55 -0000
@@ -9,14 +9,16 @@
% Ralph Becket <rafe at cs.mu.oz.au>
% Mon Feb 3 12:27:53 EST 2003
%
-% A cord is a sequence collection type supporting O(1) consing and
-% concatenation.
+% A cord is a sequence sequence type supporting O(1) consing and
+% concatenation. A cord is essentially a tree structure with data stored
+% in the leaf nodes. Joining two cords together to construct a new cord
+% is therefore an O(1) operation.
%
% This data type is intended for situations where efficient, linearised
% collection of data is required.
%
-% While this data type presents a list-like interface, deconstruction in
-% particular is not cheap - O(n) in the size of the cord.
+% While this data type presents a list-like interface, calls to list/1 and
+% head_tail/3 in particular are O(n) in the size of the cord.
%
%-----------------------------------------------------------------------------%
@@ -28,70 +30,88 @@
+ % Cords that contain the same members in the same order will not
+ % necessarily have the same representation and will, therefore,
+ % not necessarily either unify or compare as equal.
+ %
+ % The exception to this rule is that the empty cord does have a
+ % unique representation.
+ %
:- type cord(T).
- % The list of data in a cord. If datum X was added to the cord more
- % recently than datum Y then X will be closer to the head of the
- % resulting list than Y. The relative order of items added via
- % cons_list/2 is preserved.
+ % The list of data in a cord:
+ %
+ % list(empty ) = []
+ % list(from_list(Xs)) = Xs
+ % list(cons(X, C) ) = [X | list(C)]
+ % list(TA ++ TB ) = list(TA) ++ list(TB)
%
:- func list(cord(T)) = list(T).
- % The empty cord.
+ % The unique representation for the empty cord:
+ %
+ % list(empty) = []
%
:- func empty = cord(T).
- % from_list(Xs) = T <=> list(T) = Xs
+ % list(singleton(X)) = [X]
+ %
+:- func singleton(T) = cord(T).
+
+ % list(from_list(Xs)) = Xs
+ % An O(1) operation.
%
:- func from_list(list(T)) = cord(T).
- % cons(X, T0) = T <=> list(T) = [X | list(T0)]
+ % list(cons(X, C)) = [X | list(C)]
% An O(1) operation.
%
:- func cons(T, cord(T)) = cord(T).
- % cons_list(Xs, T0) = T <=> list(T) = Xs ++ list(T0)
+ % list(snoc(C, X)) = list(C) ++ [X]
% An O(1) operation.
%
-:- func cons_list(list(T), cord(T)) = cord(T).
+:- func snoc(cord(T), T) = cord(T).
- % TA ++ TB = T <=> list(T) = list(TA) ++ list(TB)
+ % list(CA ++ CB) = list(CA) ++ list(CB)
% An O(1) operation.
%
:- func cord(T) ++ cord(T) = cord(T).
- % head_tail(T0, X, T) <=> list(T0) = [X | list(T)]
- % An O(n) operation.
+ % head_tail(C0, X, C) => list(C0) = [X | list(C)]
+ % not head_tail(C0, _, _) => C0 = empty
+ % An O(n) operation, although traversing an entire cord with
+ % head_tail/3 gives O(1) amortized cost for each call.
%
:- pred head_tail(cord(T), T, cord(T)).
:- mode head_tail(in, out, out ) is semidet.
- % length(T) = list.length(list(T))
+ % length(C) = list.length(list(C))
% An O(n) operation.
%
:- func length(cord(T)) = int.
- % member(X, T) <=> list.member(X, list(T)).
+ % member(X, C) <=> list.member(X, list(C)).
%
:- pred member(T, cord(T)).
:- mode member(out, in ) is nondet.
- % map(F, T0) = T <=> list(T) = list.map(F, list(T0))
+ % list(map(F, C)) = list.map(F, list(C))
%
:- func map(func(T) = U, cord(T)) = cord(U).
- % foldl(F, T, A) = list.foldl(F, list(T), A).
+ % foldl(F, C, A) = list.foldl(F, list(C), A).
%
:- func foldl(func(T, U) = U, cord(T), U) = U.
- % foldr(F, T, A) = list.foldr(F, list(T), A).
+ % foldr(F, C, A) = list.foldr(F, list(C), A).
%
:- func foldr(func(T, U) = U, cord(T), U) = U.
- % equal(TA, TB) <=> list(TA) = list(TB).
- % An O(n) operation where n = length(TA) + length(TB).
+ % equal(CA, CB) <=> list(CA) = list(CB).
+ % An O(n) operation where n = length(CA) + length(CB).
%
% (Note: the current implementation works exactly this way.)
%
@@ -105,11 +125,13 @@
- % We impose the following invariants:
- %
- % all [T] not T = leaves([])
- % all [T] not T = branch(nil, _)
- % all [T] not T = branch(_, nil)
+ % 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
@@ -123,11 +145,15 @@
%-----------------------------------------------------------------------------%
+singleton(X) = leaf(X).
+
+%-----------------------------------------------------------------------------%
+
from_list(Xs) = ( if Xs = [] then nil else leaves(Xs) ).
%-----------------------------------------------------------------------------%
-list(T) = list_2(T, []).
+list(C) = list_2(C, []).
:- func list_2(cord(T), list(T)) = list(T).
@@ -135,40 +161,37 @@
list_2(nil, Xs) = Xs.
list_2(leaf(Y), Xs) = [Y | Xs].
list_2(leaves(Ys), Xs) = Ys ++ Xs.
-list_2(branch(TA, TB), Xs) = list_2(TA, list_2(TB, Xs)).
+list_2(branch(CA, CB), Xs) = list_2(CA, list_2(CB, Xs)).
%-----------------------------------------------------------------------------%
-cons(X, T) = ( if T = nil then leaf(X) else branch(leaf(X), T) ).
+cons(X, C) = ( if C = nil then leaf(X) else branch(leaf(X), C) ).
%-----------------------------------------------------------------------------%
-cons_list(Xs, T) = ( if Xs = [] then T
- else if T = nil then leaves(Xs)
- else branch(leaves(Xs), T)
- ).
+snoc(C, X) = ( if C = nil then leaf(X) else branch(C, leaf(X)) ).
%-----------------------------------------------------------------------------%
-TA ++ TB = ( if TA = nil then TB
- else if TB = nil then TA
- else branch(TA, TB)
+CA ++ CB = ( if CA = nil then CB
+ else if CB = nil then CA
+ else branch(CA, CB)
).
%-----------------------------------------------------------------------------%
head_tail(leaf(X), X, nil ).
-head_tail(leaves([X | Xs]), X, T ) :-
- T = ( if Xs = [] then nil else leaves(Xs) ).
+head_tail(leaves([X | Xs]), X, C ) :-
+ C = ( if Xs = [] then nil else leaves(Xs) ).
-head_tail(branch(TA0, TB), X, T ) :-
- head_tail(TA0, X, TA),
- T = TA ++ TB.
+head_tail(branch(CA0, CB), X, C ) :-
+ head_tail(CA0, X, CA),
+ C = CA ++ CB.
%-----------------------------------------------------------------------------%
-length(T) = foldl(func(_, N) = N + 1, T, 0).
+length(C) = foldl(func(_, N) = N + 1, C, 0).
%-----------------------------------------------------------------------------%
@@ -177,37 +200,37 @@
member(X, leaves(Xs)) :-
member(X, Xs).
-member(X, branch(TA, _)) :-
- member(X, TA).
+member(X, branch(CA, _)) :-
+ member(X, CA).
-member(X, branch(_, TB)) :-
- member(X, TB).
+member(X, branch(_, CB)) :-
+ member(X, CB).
%-----------------------------------------------------------------------------%
map(_, nil ) = nil.
map(F, leaf(X) ) = leaf(F(X)).
map(F, leaves(Xs) ) = leaves(map(F, Xs)).
-map(F, branch(TA, TB)) = branch(map(F, TA), map(F, TB)).
+map(F, branch(CA, CB)) = branch(map(F, CA), map(F, CB)).
%-----------------------------------------------------------------------------%
foldl(_, nil, A) = A.
foldl(F, leaf(X), A) = F(X, A).
foldl(F, leaves(Xs), A) = foldl(F, Xs, A).
-foldl(F, branch(TA, TB), A) = foldl(F, TB, foldl(F, TA, A)).
+foldl(F, branch(CA, CB), A) = foldl(F, CB, foldl(F, CA, A)).
%-----------------------------------------------------------------------------%
foldr(_, nil, A) = A.
foldr(F, leaf(X), A) = F(X, A).
foldr(F, leaves(Xs), A) = foldr(F, Xs, A).
-foldr(F, branch(TA, TB), A) = foldr(F, TA, foldr(F, TB, A)).
+foldr(F, branch(CA, CB), A) = foldr(F, CA, foldr(F, CB, A)).
%-----------------------------------------------------------------------------%
-equal(TA, TB) :-
- list(TA) = list(TB).
+equal(CA, CB) :-
+ list(CA) = list(CB).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-reviews mailing list
post: mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------
More information about the reviews
mailing list