[m-rev.] New library module: pile

[Peter Moulder]

On Wed, Feb 12, 2003 at 05:07:41PM +1100, Ralph Becket wrote:
> +* We've added a new module, cord, for collections with O(1) insertion and
> +  concatenation.

`prepending and appending' ?  `consing and concatenation' ?  (To me,
`inserting' suggests being able to add data to the middle.)

The sentence appears in two places in the NEWS file.

> +% While this data type presents a list-like interface, deconstruction in
> +% particular is not cheap - O(n) in the size of the cord.

You've already said that you prefer s/deconstruction/conversion to a
list/.

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

Not true if X was added with `++'.

Given that cord is conceptually a sequence, I would specify the
behaviours of cons etc. in terms of their effect on list.  AFAICT,
you've already done this other than for empty; I think you can simply
remove that second sentence from the comment.  The `relative order'
sentence is also redundant, though at least it's a true sentence.

Specify the behaviour of list(empty) either here or in the documentation
for empty.  I think with empty.

> +    % from_list(Xs) = T  <=>  list(T) = Xs

This is false given that you haven't used user-defined equality:
consider Xs = [a], T = cons(a, empty).  Left operand of `<=>' is false,
right operand is true.

Similarly for many other places.

Btw, why are you using the variable name `T' ?  T is usually used for
type variables (or as abbreviation of Tail).  I'd suggest C or Cord.

> +    % length(T) = list.length(list(T))
> +    % An O(n) operation.

Perhaps `Theta(n)' or `\Theta(n)' ?  array.length is O(n) too, taking
a traditional mathematical interpretation of big O.

> +    % head_tail(T0, X, T)  <=>  list(T0) = [X | list(T)]
> +    % An O(n) operation.

The worst case does indeed seem proportional to n.
Namely: S = cons(a, empty), Cord = (((...(((S ++ S) ++ S) ++ S) ++ ...) ++ S),
which becomes branch(branch(...(branch(leaf(a), leaf(a)), leaf(a)), ...).

I think it useful to state what the amortized time is though.  I haven't
worked this out (see below), but presumably it should be made to be
amortized O(1) per head_tail operation.

I believe there's a bug in the definition of head_tail.  I believe that
head_tail(branch(CA, CB), ...) must either handle CA = leaves([]) (and
more generally list(CA) = []) or ensure that leaves([]) can't occur; it
looks as if it can, e.g. the tail output of
head_tail(branch(leaves([a]), leaf(b)), Head, Tail).

I need to leave the office now, sorry for not checking.

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

Assuming head_tail works as I think it should, you could use

  equal(CA, CB):-
	foldl(head_whole_tail, list(CA), CB, empty).

  head_whole_tail(X, Whole, Tail):-
	head_tail(Whole, X, Tail).

pjm.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------