[m-dev.] [revised] for review: bintree.m -- open type /representation/

doug.auclair at logicaltypes.com doug.auclair at logicaltypes.com
Thu Feb 16 03:24:30 AEDT 2006

Dear Ralph, thank you for your response.  You wrote:

>This is not a good idea!  The bintree structure has to observe the
>ordering invariant, which is enforced by requiring users to use
>the interface presented by bintree.

Ah! Okay, given that, the below change externalizes a one-way /representation/ of bintree, which, given the revised protocol (the one-way representation/2 predicate), does not allow the internal ordering to be disturbed:

$ diff -u merc-0.12.1/library/bintree.sav merc-0.12.1/library/bintree.m
--- bintree.sav 2006-02-15 00:30:28.000000000 -0500
+++ bintree.m   2006-02-15 11:10:25.000000000 -0500
@@ -31,6 +31,14 @@
 :- import_module list, assoc_list.
 :- type bintree(K, V).
+:- type bintree_representation(K, V)
+       --->    empty_assoc_tree
+       ;       assoc_tree(
+                       K,
+                       V,
+                       bintree_representation(K, V),
+                       bintree_representation(K, V)
+               ).
 :- pred bintree__init(bintree(K, V)::uo) is det.
@@ -117,6 +125,9 @@
 :- pred bintree__balance(bintree(K, V)::in, bintree(K, V)::out) is det.
 :- func bintree__balance(bintree(K, V)) = bintree(K, V).
+:- pred bintree.representation(bintree(K, V)::in,
+                              bintree_representation(K, V)::out) is det.
 :- implementation.
@@ -550,3 +561,9 @@
 bintree__balance(BT1) = BT2 :-
        bintree__balance(BT1, BT2).
+bintree.representation(empty, empty_assoc_tree).
+bintree.representation(tree(K, V, Left, Right), assoc_tree(K, B, L1, R1)) :-
+  bintree.representation(Left, L1),
+  bintree.representation(Right, R1).
----- end diff -u

>You haven't explained why you want to see the structure of the bintree.
>If you make a good enough case, we'll happily extend the interface to
>accommodate you without compromising the bintree invariants.

The above set of changes does not compromise the bintree invariants, so I hope this resolves the issue.  As for the "why", due to constraints on me from the client, I can neither discuss them nor their business process -- I would need to get into their business process to produce a  relevant example for the changes.  So, I must stand by my initial example and need: different kinds of traversal over the structure of the type.  Sorry.

Doug Auclair

mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au

More information about the developers mailing list