🚀 go-pugleaf

Here is a problem/challenge:  Say you have two vectors A and B of
length n, and both of them are in ascending numeric order.  Write an
APL expression which sums those elements of B which occur somewhere in
A, and which operates in linear time.  Alternatively, prove that there
is no such APL expression.  (I have not solved this problem, but it
seems to me that the latter alternative more likely.)

There are a few ways to appropriately restrict the set of allowable
expressions.  For instance, there is an annual contest to take the
digits of the current year and write the shortest expressions involving
those digits which evaluate to each of the numbers from 1 to 100.  The
contest has certain rules about permissible APL expressions.

Assuming that "epsilon" operates in (m+n)log( n ) time, an nlog( n )
expression is:

	+/( B epsilon A ) / B

In a conventional programming language, one can write a loop which in
effect merges the two lists, and detects elements of B which occur in
A.  Of course, such a program would be unintelligible without careful
study, whereas anyone who knows APL would immediately recognize what
the above phrase does; in fact, the phrase might even be taken as a
specification of the problem.

Several researchers are active in "program transformation" techniques.
Might it be possible to extend APL so that one could take an easily
understandable APL expression and algebraically transform it into an
equivalent efficient but perhaps unintelligible expression?

				 - Greg Johnson
				   gjohnson@cornell