[m-rev.] New library module: pile

[Fergus Henderson]

On 12-Feb-2003, Ralph Becket <rafe at cs.mu.OZ.AU> wrote:
> Estimated hours taken: 4
> Branches: main
> 
> Added a new library module, cord, for a collection type supporting O(1)
> insertion and concatenation.

I suggest s/collection/sequence/
or s/collection/sequence collection/

> Index: NEWS
...
> +* We've added a new module, cord, for collections with O(1) insertion and
> +  concatenation.

Likewise here.

>  Changes to the Mercury standard library:
> +
> +* We've added a new module, cord, for collections with O(1) insertion and
> +  concatenation.

And here.  It's probably worth adding a sentence or two explaining the
implementation of this type here (and also to the documentation at
the start of cord.m).

Also, the documentation in the cord module -- either at the start,
or at the declaration of the cord(T) type -- should explain the
semantics of unification and comparison for cords.

> +    % The empty cord.
> +    %
> +:- func empty = cord(T).

I suggest also adding

	% T = empty <=> list(T) = []

> +    % from_list(Xs) = T  <=>  list(T) = Xs
> +    %
> +:- func from_list(list(T)) = cord(T).

The documentation for this function is incorrect,
because it assumes the abstract semantics for equality,
but equality on cords is equality of representations
rather than equivalence of sequences.
There reverse direction of the implication does not hold.

The simplest fix is to change "<=>" to "=>".

All of the other functions and predicates which return cords have the
same problem, except perhaps cord.empty (since the data structure
invariants mean that there is only one representation of the empty
cord).  The fix of changing "<=>" to "=>" works for all of those too,
except that for head_tail/3, you should also add the axiom

	(not head_tail(T0, _, _)) => list(T0) = []

> +    % 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.

If you traverse the whole cord with head_tail,
the complexity for this is O(n) total,
i.e. O(1) amortized, isn't it?

If so, I think this is worth documenting.

> +:- 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)).

It would help to document the rationale for these invariants.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------