[m-rev.] New library module: pile
Ralph Becket
rafe at cs.mu.OZ.AU
Wed Feb 12 17:07:41 AEDT 2003
Okay, here's the final diff with test case. If I don't get any
complaints in the next day or so I'll check it in as is.
Estimated hours taken: 4
Branches: main
Added a new library module, cord, for a collection type supporting O(1)
insertion and concatenation.
NEWS:
Report the new addition.
library/cord.m:
Added.
tests/hard_coded/Mmakefile:
tests/hard_coded/test_cord.m:
tests/hard_coded/test_cord.exp:
Added a test case for the new cord module.
Index: NEWS
===================================================================
RCS file: /home/mercury1/repository/mercury/NEWS,v
retrieving revision 1.299
diff -u -r1.299 NEWS
--- NEWS 30 Jan 2003 05:59:16 -0000 1.299
+++ NEWS 12 Feb 2003 05:57:39 -0000
@@ -16,7 +16,8 @@
with `mmc --make'.
Changes to the Mercury standard library:
-* Nothing yet.
+* We've added a new module, cord, for collections with O(1) insertion and
+ concatenation.
Portability improvements:
* Nothing yet.
@@ -60,6 +61,9 @@
chapter of the Mercury Language Reference Manual.
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 library module, `array2d'.
Index: library/cord.m
===================================================================
RCS file: library/cord.m
diff -N library/cord.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ library/cord.m 12 Feb 2003 05:38:34 -0000
@@ -0,0 +1,213 @@
+%-----------------------------------------------------------------------------%
+% cord.m
+% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+%---------------------------------------------------------------------------%
+% Copyright (C) 2002 The University of Melbourne.
+% This file may only be copied under the terms of the GNU Library General
+% Public License - see the file COPYING.LIB in the Mercury distribution.
+%---------------------------------------------------------------------------%
+% 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.
+%
+% 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.
+%
+%-----------------------------------------------------------------------------%
+
+:- module cord.
+
+:- interface.
+
+:- import_module list, int.
+
+
+
+:- 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.
+ %
+:- func list(cord(T)) = list(T).
+
+ % The empty cord.
+ %
+:- func empty = cord(T).
+
+ % from_list(Xs) = T <=> list(T) = Xs
+ %
+:- func from_list(list(T)) = cord(T).
+
+ % cons(X, T0) = T <=> list(T) = [X | list(T0)]
+ % An O(1) operation.
+ %
+:- func cons(T, cord(T)) = cord(T).
+
+ % cons_list(Xs, T0) = T <=> list(T) = Xs ++ list(T0)
+ % An O(1) operation.
+ %
+:- func cons_list(list(T), cord(T)) = cord(T).
+
+ % TA ++ TB = T <=> list(T) = list(TA) ++ list(TB)
+ % 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.
+ %
+:- pred head_tail(cord(T), T, cord(T)).
+:- mode head_tail(in, out, out ) is semidet.
+
+ % length(T) = list.length(list(T))
+ % An O(n) operation.
+ %
+:- func length(cord(T)) = int.
+
+ % member(X, T) <=> list.member(X, list(T)).
+ %
+:- pred member(T, cord(T)).
+:- mode member(out, in ) is nondet.
+
+ % map(F, T0) = T <=> list(T) = list.map(F, list(T0))
+ %
+:- func map(func(T) = U, cord(T)) = cord(U).
+
+ % foldl(F, T, A) = list.foldl(F, list(T), A).
+ %
+:- func foldl(func(T, U) = U, cord(T), U) = U.
+
+ % foldr(F, T, A) = list.foldr(F, list(T), 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).
+ %
+ % (Note: the current implementation works exactly this way.)
+ %
+:- pred equal(cord(T), cord(T)).
+:- mode equal(in, in ) is semidet.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+
+
+ % We impose the following invariants:
+ %
+ % all [T] not T = leaves([])
+ % all [T] not T = branch(nil, _)
+ % all [T] not T = branch(_, nil)
+ %
+:- type cord(T)
+ ---> nil
+ ; leaf(T)
+ ; leaves(list(T))
+ ; branch(cord(T), cord(T)).
+
+%-----------------------------------------------------------------------------%
+
+empty = nil.
+
+%-----------------------------------------------------------------------------%
+
+from_list(Xs) = ( if Xs = [] then nil else leaves(Xs) ).
+
+%-----------------------------------------------------------------------------%
+
+list(T) = list_2(T, []).
+
+
+:- func list_2(cord(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(TA, TB), Xs) = list_2(TA, list_2(TB, Xs)).
+
+%-----------------------------------------------------------------------------%
+
+cons(X, T) = ( if T = nil then leaf(X) else branch(leaf(X), T) ).
+
+%-----------------------------------------------------------------------------%
+
+cons_list(Xs, T) = ( if Xs = [] then T
+ else if T = nil then leaves(Xs)
+ else branch(leaves(Xs), T)
+ ).
+
+%-----------------------------------------------------------------------------%
+
+TA ++ TB = ( if TA = nil then TB
+ else if TB = nil then TA
+ else branch(TA, TB)
+ ).
+
+%-----------------------------------------------------------------------------%
+
+head_tail(leaf(X), X, nil ).
+
+head_tail(leaves([X | Xs]), X, T ) :-
+ T = ( if Xs = [] then nil else leaves(Xs) ).
+
+head_tail(branch(TA0, TB), X, T ) :-
+ head_tail(TA0, X, TA),
+ T = TA ++ TB.
+
+%-----------------------------------------------------------------------------%
+
+length(T) = foldl(func(_, N) = N + 1, T, 0).
+
+%-----------------------------------------------------------------------------%
+
+member(X, leaf(X)).
+
+member(X, leaves(Xs)) :-
+ member(X, Xs).
+
+member(X, branch(TA, _)) :-
+ member(X, TA).
+
+member(X, branch(_, TB)) :-
+ member(X, TB).
+
+%-----------------------------------------------------------------------------%
+
+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)).
+
+%-----------------------------------------------------------------------------%
+
+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)).
+
+%-----------------------------------------------------------------------------%
+
+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)).
+
+%-----------------------------------------------------------------------------%
+
+equal(TA, TB) :-
+ list(TA) = list(TB).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
Index: tests/hard_coded/Mmakefile
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/Mmakefile,v
retrieving revision 1.185
diff -u -r1.185 Mmakefile
--- tests/hard_coded/Mmakefile 7 Feb 2003 03:55:36 -0000 1.185
+++ tests/hard_coded/Mmakefile 12 Feb 2003 05:56:48 -0000
@@ -141,9 +141,10 @@
target_mlobjs \
term_io_test \
term_to_univ_test \
+ test_array2d \
test_bitset \
+ test_cord \
test_imported_no_tag \
- test_array2d \
tim_qual1 \
time_test \
tuple_test \
Index: tests/hard_coded/test_cord.exp
===================================================================
RCS file: tests/hard_coded/test_cord.exp
diff -N tests/hard_coded/test_cord.exp
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/test_cord.exp 12 Feb 2003 05:41:34 -0000
@@ -0,0 +1,31 @@
+
+cords:
+Z = nil
+A = leaf('a')
+B = leaves(['b'])
+AB = branch(leaf('a'), leaves(['b']))
+BA = branch(leaves(['b']), leaf('a'))
+ABA1 = branch(leaf('a'), branch(leaves(['b']), leaf('a')))
+ABA2 = branch(branch(leaf('a'), leaves(['b'])), leaf('a'))
+BAB1 = branch(leaves(['b']), branch(leaf('a'), leaves(['b'])))
+BAB2 = branch(branch(leaves(['b']), leaf('a')), leaves(['b']))
+ABBA = branch(branch(leaf('a'), leaves(['b'])), branch(leaves(['b']), leaf('a')))
+BAAB = branch(branch(leaves(['b']), leaf('a')), branch(leaf('a'), leaves(['b'])))
+
+construction: ok
+
+concatenation: ok
+
+equals: ok
+
+identity: ok
+
+length: ok
+
+membership: ok
+
+map: ok
+
+foldl: ok
+
+foldr: ok
Index: tests/hard_coded/test_cord.m
===================================================================
RCS file: tests/hard_coded/test_cord.m
diff -N tests/hard_coded/test_cord.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/test_cord.m 12 Feb 2003 05:40:44 -0000
@@ -0,0 +1,178 @@
+%-----------------------------------------------------------------------------%
+% test_cord.m
+% Ralph Becket <rafe at cs.mu.oz.au>
+% Tue Feb 11 16:05:29 EST 2003
+% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+%
+%-----------------------------------------------------------------------------%
+
+:- module test_cord.
+
+:- interface.
+
+:- import_module io.
+
+
+
+:- pred main(io::di, io::uo) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module cord, list, string, std_util.
+
+%-----------------------------------------------------------------------------%
+
+main -->
+
+ { Z = empty,
+ A = cons(a, Z),
+ B = from_list([b]),
+ AB = A ++ B,
+ BA = B ++ A,
+ ABA1 = A ++ BA,
+ ABA2 = AB ++ A,
+ BAB1 = B ++ AB,
+ BAB2 = BA ++ B,
+ ABBA = AB ++ BA,
+ BAAB = BA ++ AB
+ },
+
+ io.format("\ncords:\n", []),
+ io.format("Z = ", []), io.print(Z ), io.nl,
+ io.format("A = ", []), io.print(A ), io.nl,
+ io.format("B = ", []), io.print(B ), io.nl,
+ io.format("AB = ", []), io.print(AB ), io.nl,
+ io.format("BA = ", []), io.print(BA ), io.nl,
+ io.format("ABA1 = ", []), io.print(ABA1), io.nl,
+ io.format("ABA2 = ", []), io.print(ABA2), io.nl,
+ io.format("BAB1 = ", []), io.print(BAB1), io.nl,
+ io.format("BAB2 = ", []), io.print(BAB2), io.nl,
+ io.format("ABBA = ", []), io.print(ABBA), io.nl,
+ io.format("BAAB = ", []), io.print(BAAB), io.nl,
+
+ { ConstructionResult =
+ ( if list(Z) \= [] then "list(Z) \\= []"
+ else if list(A) \= [a] then "list(A) \\= [a]"
+ else if list(B) \= [b] then "list(B) \\= [b]"
+ else "ok"
+ )
+ },
+
+ io.format("\nconstruction: %s\n", [s(ConstructionResult)]),
+
+ { ConcatenationResult =
+ ( if list(AB) \= [a, b] then "list(AB) \\= [a, b]"
+ else if list(BA) \= [b, a] then "list(BA) \\= [b, a]"
+ else if list(ABA1) \= [a, b, a] then "list(ABA1) \\= [a, b, a]"
+ else if list(ABA2) \= [a, b, a] then "list(ABA2) \\= [a, b, a]"
+ else if list(BAB1) \= [b, a, b] then "list(BAB1) \\= [b, a, b]"
+ else if list(BAB2) \= [b, a, b] then "list(BAB2) \\= [b, a, b]"
+ else if list(ABBA) \= [a, b, b, a] then "list(ABBA) \\= [a, b, b, a]"
+ else if list(BAAB) \= [b, a, a, b] then "list(BAAB) \\= [b, a, a, b]"
+ else "ok"
+ )
+ },
+
+ io.format("\nconcatenation: %s\n", [s(ConcatenationResult)]),
+
+ { EqualsResult =
+ ( if not equal(ABA1, ABA2) then "not equal(ABA1, ABA2)"
+ else if not equal(BAB1, BAB2) then "not equal(BAB1, BAB2)"
+ else "ok"
+ )
+ },
+
+ io.format("\nequals: %s\n", [s(EqualsResult)]),
+
+ { IdentityResult =
+ ( if AB ++ empty \= AB then "AB ++ empty \\= AB "
+ else if BA ++ empty \= BA then "BA ++ empty \\= BA "
+ else if ABA1 ++ empty \= ABA1 then "ABA1 ++ empty \\= ABA1"
+ else if ABA2 ++ empty \= ABA2 then "ABA2 ++ empty \\= ABA2"
+ else if BAB1 ++ empty \= BAB1 then "BAB1 ++ empty \\= BAB1"
+ else if BAB2 ++ empty \= BAB2 then "BAB2 ++ empty \\= BAB2"
+ else if ABBA ++ empty \= ABBA then "ABBA ++ empty \\= ABBA"
+ else if BAAB ++ empty \= BAAB then "BAAB ++ empty \\= BAAB"
+
+ else if empty ++ AB \= AB then "empty ++ AB \\= AB "
+ else if empty ++ BA \= BA then "empty ++ BA \\= BA "
+ else if empty ++ ABA1 \= ABA1 then "empty ++ ABA1 \\= ABA1"
+ else if empty ++ ABA2 \= ABA2 then "empty ++ ABA2 \\= ABA2"
+ else if empty ++ BAB1 \= BAB1 then "empty ++ BAB1 \\= BAB1"
+ else if empty ++ BAB2 \= BAB2 then "empty ++ BAB2 \\= BAB2"
+ else if empty ++ ABBA \= ABBA then "empty ++ ABBA \\= ABBA"
+ else if empty ++ BAAB \= BAAB then "empty ++ BAAB \\= BAAB"
+
+ else "ok"
+ )
+ },
+
+ io.format("\nidentity: %s\n", [s(IdentityResult)]),
+
+ { LengthResult =
+ ( if length(Z) \= 0 then "list(Z) \\= 0"
+ else if length(A) \= 1 then "list(A) \\= 1"
+ else if length(B) \= 1 then "list(B) \\= 1"
+ else if length(AB) \= 2 then "list(AB) \\= 2"
+ else if length(BA) \= 2 then "list(BA) \\= 2"
+ else if length(ABA1) \= 3 then "list(ABA1) \\= 3"
+ else if length(ABA2) \= 3 then "list(ABA2) \\= 3"
+ else if length(BAB1) \= 3 then "list(BAB1) \\= 3"
+ else if length(BAB2) \= 3 then "list(BAB2) \\= 3"
+ else if length(ABBA) \= 4 then "list(ABBA) \\= 4"
+ else if length(BAAB) \= 4 then "list(BAAB) \\= 4"
+ else "ok"
+ )
+ },
+
+ io.format("\nlength: %s\n", [s(LengthResult)]),
+
+ { MemberResult =
+ ( if solutions((pred(X::out) is nondet :- member(X, ABBA))) \= [a, b]
+ then "members(ABBA) \\= [a, b]"
+ else "ok"
+ )
+ },
+
+ io.format("\nmembership: %s\n", [s(MemberResult)]),
+
+ { MapResult =
+ ( if list(map(func(X) = ( if X = a then p else q ), AB)) \= [p, q]
+ then "map(|a -> p, b -> q|, AB) \\= [p, q]"
+ else "ok"
+ )
+ },
+
+ io.format("\nmap: %s\n", [s(MapResult)]),
+
+ { FoldlResult =
+ ( if foldl(func(X, Xs) = [X | Xs], AB, []) \= [b, a]
+ then "foldl(cons, AB, []) \\= [b, a]"
+ else
+ if foldl(func(X, Xs) = [X | Xs], from_list([a, b]), []) \= [b, a]
+ then "foldl(cons, from_list([a, b]), []) \\= [b, a]"
+ else "ok"
+ )
+ },
+
+ io.format("\nfoldl: %s\n", [s(FoldlResult)]),
+
+ { FoldrResult =
+ ( if foldr(func(X, Xs) = [X | Xs], AB, []) \= [a, b]
+ then "foldr(cons, AB, []) \\= [a, b]"
+ else
+ if foldr(func(X, Xs) = [X | Xs], from_list([a, b]), []) \= [a, b]
+ then "foldr(cons, from_list([a, b]), []) \\= [a, b]"
+ else "ok"
+ )
+ },
+
+ io.format("\nfoldr: %s\n", [s(FoldrResult)]),
+
+ [].
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
--------------------------------------------------------------------------
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