[m-rev.] New library module: pile

[Ralph Becket]

I've wanted this sort of thing often enough that I think it should go
in the library.  I'd be happy to change the name etc. if anyone has a
better suggestion.  I'll add test cases if it's accepted.

Question: does this need some sort of deconstruction mechanism other
than list/1?

Estimated hours taken: 3
Branches: main

Added a new library module, pile, for a collection type supporting O(1)
insertion and concatenation.

NEWS:
	Report the new addition.

library/pile.m:
	Added.

Index: NEWS
===================================================================
RCS file: /home/mercury1/repository/mercury/NEWS,v
retrieving revision 1.298
diff -u -r1.298 NEWS
--- NEWS	27 Jan 2003 09:20:42 -0000	1.298
+++ NEWS	5 Feb 2003 02:44:12 -0000
@@ -16,7 +16,12 @@
   with `mmc --make'.
 
 Changes to the Mercury standard library:
-* Nothing yet.
+
+* We've added a new module, pile, for collections with O(1) insertion and
+  concatenation.
 
 Portability improvements:
 * Nothing yet.
@@ -60,6 +65,13 @@
   chapter of the Mercury Language Reference Manual.
 
 Changes to the Mercury standard library:
+
+* We've added a new module, pile, for collections with O(1) insertion and
+  concatenation.
 
 * We've added a new library module, `array2d'.
 
Index: library/pile.m
===================================================================
RCS file: library/pile.m
diff -N library/pile.m
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ library/pile.m	5 Feb 2003 02:05:30 -0000
@@ -0,0 +1,153 @@
+%-----------------------------------------------------------------------------%
+% pile.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 pile is a collection type supporting O(1) consing and
+% concatenation.  Deconstruction, however, is O(n) for a
+% pile containing n members.
+%
+%-----------------------------------------------------------------------------%
+
+:- module pile.
+
+:- interface.
+
+:- import_module list.
+
+
+
+:- type pile(T).
+
+
+
+    % The list of data in a pile.  If datum X was added to the pile 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(pile(T)) = list(T).
+
+    % The empty pile.
+    %
+:- func empty = pile(T).
+
+    % cons(X, T0) = T  <=>  list(T) = [X | list(T0)]
+    % An O(1) operation.
+    %
+:- func cons(T, pile(T)) = pile(T).
+
+    % cons_list(Xs, T0) = T  <=>  list(T) = Xs ++ list(T0)
+    % An O(1) operation.
+    %
+:- func cons_list(list(T), pile(T)) = pile(T).
+
+    % TA ++ TB = T  <=>  list(T) = list(TA) ++ list(TB)
+    % An O(1) operation.
+    %
+:- func pile(T) ++ pile(T) = pile(T).
+
+    % member(X, T) <=> member(X, list(T)).
+    %
+:- pred member(T,   pile(T)).
+:- mode member(out, in     ) is nondet.
+
+    % map(F, T) is identical to T except that every leaf
+    % datum X in T is substituted with F(X).
+    %
+:- func map(func(T) = U, pile(T)) = pile(U).
+
+    % foldl(F, T, A) = foldl(F, list(T), A).
+    %
+:- func foldl(func(T, U) = U, pile(T), U) = U.
+
+    % foldr(F, T, A) = foldr(F, list(T), A).
+    %
+:- func foldr(func(T, U) = U, pile(T), U) = U.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+
+
+:- type pile(T)
+    --->    nil
+    ;       leaf(T)
+    ;       leaves(list(T))
+    ;       branch(pile(T), pile(T)).
+
+%-----------------------------------------------------------------------------%
+
+empty = nil.
+
+%-----------------------------------------------------------------------------%
+
+list(T) = list_2(T, []).
+
+
+:- func list_2(pile(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 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)
+           ).
+
+%-----------------------------------------------------------------------------%
+
+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, TB, foldr(F, TA, A)).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------