🚀 go-pugleaf

It does of course depend on your model of memory as to whether the C is
linear time.... one might argue that memory is logarithmic (based on the
number of gates required to decode an address) or cube-root-n (based on
the number of physically-minimal-memory-cells that one can pack in a given
space. In practice it seems to be lumpy-logarithmic.

However, let us be conventional, and suppose we have constant time  access.
It is difficult to see how to render the random permutation algorithm  into
a linear  time function.  The problem  is  that an  array is  a  (memoised)
function on a sub-range  of the integers  (or cartesian products  thereof).
Thus of course the O(1) access time available from the old POP-2  treatment
of arrays (to my mind better than the Haskell proposal) doesn't help, since
it takes O(n)  time to  make such  an array, and  you have  to remake  it n
times. [Of  course, a  cunning compiler  ought to  be able  to  transform a
log-time functional program into a linear time non-functional one.]

Incidentally, the POP-2/POP-11 treatment of arrays-as-functions allows
you to write a constant time product of permutations in a 'quasi-lazy' way.
If n is fixed then the function product:

  P1<>P2

is permutation product.  If you want n to be variable, we need something
like the following:

/* a pure function defined using the non-functional capabilities.
Operator precedence = 4. */

define 4 F with_props Props;
  lvars F,Props,F1 = copy(F);
  Props -> pdprops(F1);
enddefine;

vars domain = pdprops;

/* constant time permutation product */

define prod_perm(P1,P2);
    P1<>P2 with_props domain(P1)
enddefine;


/* linear time permutation product */

define prod_perm(P1,P2);
  lvars n = domain(P1);
  newarray([%1,n%], P1<>P2) with_props n);
enddefine;





Robin.