[m-dev.] Suggested interface for sequence types in lib-v2

[Ralph Becket]

>From Fergus Henderson on 20/10/2000 14:52:04
> You want
> 
> 	:- func semidet_head(seq(T)) = T is semidet.
> 	                                ^^^^^^^^^^^
Doh.
> 
> But see below about naming conventions.
> 
> > :- func but_last(seq(T)) = seq(T).
> > :- func semidet_but_last(seq(T)) = seq(T) is semidet.
> 
> What is that supposed to do?

These are supposed to return all but the last member of a
sequence, so if S is a non-empty sequence then

	S = snoc(last(S), but_last(S))

> Is it supposed to return the second-last element in the sequence (if any)?
> If so, I think it would be better to name it `second_last'.
> But I don't think that it is useful enough to justify inclusion
> in the standard library.

The intended meaning is important for double-ended sequence
types.  Providing naive default implementations should
relieve the library author of the burden of filling
everything in, if this is otherwise a problem.

> > :- pred project_member(seq(T)::in, T::out) is nondet.
> 
> What is that supposed to do?
> How does it differ from `member'?

Several `solutions' style predicates expect the output argument
to be the last one.  I included project_member/2 for this
reason.  It's debatable whether or not it's useful enough to
warrant inclusion, but if we supply the obvious default
implementation based on member/2 then we should be okay.

> > :- func rev_append(seq(T), seq(T)) = seq(T).
> 
> What is that supposed to do?

	rev_append(S1, S2) = reverse(S1) ++ S2

The point is that there's often a more efficient implementation
of this operations than the RHS.  e.g. for lists:

rev_append([], S2) = S2.
rev_append([S | S1], S2) = rev_append(S1, [S | S2]).

> >                                         % XXX Is this really useful?
> > :- func condense_map(func(T1) = seq(T2), seq(T1)) = seq(T2).
> 
> Is this just
> 
> 	condense_map(F, S) = condense(map(F, S)).
> 
> ?
> If so, I don't think it is worth including, unless there
> are some sequences for which condense_map(F, S) can be implemented
> more efficiently than condense(map(F, S)).  Off-hand I don't know
> of any such sequences.

condense_map/2 is there to avoid construction of an intermediate
sequence.

This is part of a larger problem that e.g. the people at Mission
Critical have come across.  In C++ one can typically traverse a large 
library structure using iterators; in Mercury one usually has to
flatten such a thing into a sequence (list) and then traverse that.
If your structure is *very* large then this can be costly.  While the
library has been extended to include more mapping operations etc., the
suite of such operations provided so far isn't comprehensive.

I wonder if this is justification for requiring provision of the means 
to traverse structures lazily?

> > % REMOVING MEMBERS
> > 
> >                                         % Error unless S `contains` X.
> > :- func delete_first(T, seq(T)) = seq(T).
> 
> I think that should be semidet.
> A det `delete_first_det' might be useful, but
> I think the semidet one is probably more useful.

Okay.  The convention I was using was that operation foo would be
det while semidet_foo would be semidet.  In this case it's not
clear whether the proper functionality is to delete the first
x if one is present, otherwise do nothing.  Hmmm...

> > % INDEX BASED OPERATIONS
> >                                         % index_in(S, head(S)) = 0.
> > :- func index_in(seq(T), T) = int.      % Error unless S `contains` X.
> > :- func semidet_index_in(seq(T), T) = int is semidet.
> 
> Our traditional naming scheme for these kind of things has been
> for the semidet one to have the unadorned name, and for the
> det one to get a `_det' suffix.  I think this is a better idea,
> since the explicit `_det' suffix serves as a hint that the procedure
> might call error/1 in some circumstances, and so the programmer
> had better be careful to ensure that the parameters at each call
> meet the preconditions.

I think that is true for predicates, but that the reverse should
be the case for functions.  After all, one usually expects a function
to be deterministic.  I'm prepared to be converted on this one...
anybody else have any strong feelings?

> > :- func lookup(seq(T), int) = T.        % Error unless 0 =< I <
length(S).
> > :- func seq(T) @ int = T.               % Synonym for lookup/2.
> > :- func semidet_lookup(seq(T), int) = T.
> 
> I'd rather semidet_lookup be named `search'.
> This is used very frequently.

Okay.

> >     % replace(S, I, X) = take_n(I - 1, S) ++ cons(X, drop_up_to_n(I, S))
> >     % Error unless 0 =< I < length(S).
> >     %
> > :- func replace(seq(T), int, T) = seq(T).
> > 
> >     % change(S, I, F) = take_n(I - 1, S) ++ cons(F(lookup(S, I)),
drop_n(I,
> > S))
> >     % Error unless 0 =< I < length(S).
> >     %
> > :- func change(seq(T), int, func(T) = T) = seq(T).
> 
> So is change(S, I, F) = replace(S, I, F(S `lookup` I))?
> If so, then (a) that would be a simpler way of documenting it
> and (b) is it really worth including in the standard library?

I've changed the comment to (a).  The question here is
whether or not there are enough random-access sequence types for
which there are more efficient implementations than the RHS to
justify the inclusion of change/3.

The jury may still be out on this one, but for, say, bt_arrays and
maps change/3 would be handy and more efficient.

I've basically been following Okasaki's approach in that if a
class contains a large-enough subset of types for which there is
an efficient implementation of a reasonably common idiom then
that should go in the spec.

Again, I'm prepared to be convinced that I'm wrong.

Ralph

--
Ralph Becket      |      MSR Cambridge      |      rbeck at microsoft.com 

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