home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / lang / function / 1508 < prev    next >
Encoding:
Internet Message Format  |  1993-01-11  |  2.1 KB
  1. Path: sparky!uunet!noc.near.net!nic.umass.edu!dime!roo.cs.umass.edu!pop
  2. From: pop@cs.umass.edu ( Robin Popplestone )
  3. Newsgroups: comp.lang.functional
  4. Subject: Permutations
  5. Message-ID: <58538@dime.cs.umass.edu>
  6. Date: 11 Jan 93 14:43:34 GMT
  7. Sender: news@dime.cs.umass.edu
  8. Organization: University of Massachusetts, Amherst
  9. Lines: 55
  10. Originator: pop@roo.cs.umass.edu
  11.  
  12.  
  13. It does of course depend on your model of memory as to whether the C is
  14. linear time.... one might argue that memory is logarithmic (based on the
  15. number of gates required to decode an address) or cube-root-n (based on
  16. the number of physically-minimal-memory-cells that one can pack in a given
  17. space. In practice it seems to be lumpy-logarithmic.
  18.  
  19. However, let us be conventional, and suppose we have constant time  access.
  20. It is difficult to see how to render the random permutation algorithm  into
  21. a linear  time function.  The problem  is  that an  array is  a  (memoised)
  22. function on a sub-range  of the integers  (or cartesian products  thereof).
  23. Thus of course the O(1) access time available from the old POP-2  treatment
  24. of arrays (to my mind better than the Haskell proposal) doesn't help, since
  25. it takes O(n)  time to  make such  an array, and  you have  to remake  it n
  26. times. [Of  course, a  cunning compiler  ought to  be able  to  transform a
  27. log-time functional program into a linear time non-functional one.]
  28.  
  29. Incidentally, the POP-2/POP-11 treatment of arrays-as-functions allows
  30. you to write a constant time product of permutations in a 'quasi-lazy' way.
  31. If n is fixed then the function product:
  32.  
  33.   P1<>P2
  34.  
  35. is permutation product.  If you want n to be variable, we need something
  36. like the following:
  37.  
  38. /* a pure function defined using the non-functional capabilities.
  39. Operator precedence = 4. */
  40.  
  41. define 4 F with_props Props;
  42.   lvars F,Props,F1 = copy(F);
  43.   Props -> pdprops(F1);
  44. enddefine;
  45.  
  46. vars domain = pdprops;
  47.  
  48. /* constant time permutation product */
  49.  
  50. define prod_perm(P1,P2);
  51.     P1<>P2 with_props domain(P1)
  52. enddefine;
  53.  
  54.  
  55. /* linear time permutation product */
  56.  
  57. define prod_perm(P1,P2);
  58.   lvars n = domain(P1);
  59.   newarray([%1,n%], P1<>P2) with_props n);
  60. enddefine;
  61.  
  62.  
  63.  
  64.  
  65.  
  66. Robin.
  67.