[m-dev.] Proposal: sequence quantification

[Ralph Becket]

>From Peter Schachte on 03/01/2001 00:52:16
> We propose a specialized form of quantification that fills the roles
> of the map/fold/filter higher order predicates (and all their
> combinations) in a flexible and convenient way.

My first impression is that this is a Good Idea.  I've long
wished for some declarative way of describing non-trivial iteration
that didn't get bogged down in lambdas and auxiliary functions.

I'd really like to see some details of the transformation.

> Generally the quantified goal will compute `next S' from S in some
> way, but it need not.  For example, one could find the last element of
> a sequence like this:
> 
> 	for E in Sequence as Curr initially no finally yes(LastElt) ::
> 		next Curr = yes(E)

Presumably this could also be written as

	for E in Sequence as Curr initially E finally LastElt ::
		next Curr = E

or would it have to be written as

	Sequence = [Init | _],
	for E in Sequence as Curr initially Init finally LastElt ::
		next Curr = E

> This says that Result is the elements of List which are greater than
> 0.  This is equivalent to a call to list__filter.  A more interesting
> example is:
> 
> 	for P in List when P > 0 
> 	 as N in List when N < 0 
>          as S in Result 
> 	 :: S = P + N

`as' requires both L and R sequences to be the same length - does it
fail quietly if they are not (i.e. is semidet code generated) or is
an exception thrown?  If the former, I think there is scope for a
version with the latter behaviour as that will be quite common
(call it `det_for' or something, or maybe make `for' the det case).

> which says that Result is the sequence of sums of the corresponding
> positive and negative elements of List.  The `when' operator employs a
> bit of syntactic sugar:  `E in List when E > 0' is equivalent to `E in
> filter(List, (pred(X::in) is semidet :- X > 0))', but easier to write.
> 
> Similar are `while' and `until', which take the front of a sequence up
> to but not including the first element for which a condition fails
> (succeeds).  For example:
> 
> 	for E in List while E >= 0 as S initially 0 finally Sum 
> 		:: next S = S + E
> 
> or equivalently,
> 
> 	for E in List until E < 0 as S initially 0 finally Sum 
> 		:: next S = S + E
> 
> which sum the elements of List up to the first negative element.
> Nonnegative elements of List following the first negative one are not
> summed.  Again, this construct is syntactic sugar for a simple
> higher-order sequence operation which takes the front of the sequence.
> 
> Similarly, the `once' operator drops the front of the sequence up to
> the point that a predicate holds, for example:
> 
> 	for E in List once E >= 0 as S initially 0 finally Sum 
> 		:: next S = S + E

Can these be composed, as in

	for E in List once E >=0 while E < 10 ...

On the matter of the transformation only applying to lists in the
first instance, I presume that `X initially A finally Z' will be
an accumulator rather than lead to the creation of a list?  Or is
that necessary?

Cheers,

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