home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / lang / function / 1503 < prev    next >
Encoding:
Internet Message Format  |  1993-01-10  |  1.7 KB
  1. Path: sparky!uunet!mcsun!sunic!chalmers.se!cs.chalmers.se!augustss
  2. From: augustss@cs.chalmers.se (Lennart Augustsson)
  3. Newsgroups: comp.lang.functional
  4. Subject: Re: Random permutations, linear time, fully functional?
  5. Keywords: n
  6. Message-ID: <1993Jan10.195938.27864@cs.chalmers.se>
  7. Date: 10 Jan 93 19:59:38 GMT
  8. References: <C0KG2y.HvE@dcs.ed.ac.uk>
  9. Sender: news@cs.chalmers.se (News administrator)
  10. Organization: Chalmers University of Technology
  11. Lines: 25
  12.  
  13. >Following a long and heated discussion on the topic in a local
  14. >newsgroup in which the local ML experts have come up hands empty
  15. >(surprising given this is Edinburgh), I'm looking for fully functional
  16. >ways of solving certain permutation problems which imperative languages
  17. >like C can solve in linear time.  In particular, I'd like to be able to
  18. >compose and invert permutations and generate random ones in linear
  19. >time.
  20. Of course you can do it, it all depends on what primitive operations
  21. you have available and what time they take.  Assuming that you
  22. have updateable arrays with O(1) index and update it's trivial.
  23. (The arrays can be packaged in any way you like to make them pure:
  24. as a stream-to-stream function (lookup/index in, value out), as a
  25. state monad, as version arrays, ...).  I don't consider having those
  26. as primitive operations as cheating, all imperative languages have
  27. them so why shouldn't we?
  28.  
  29. If, on the other hand, you only allow the pure lambda-calculus as
  30. the programming language (with suger if you want), then I kind of doubt
  31. that it can be done.  (Unless you have a constant time beta reduction
  32. step and can come up with some clever coding of arrays.)
  33.  
  34. -- 
  35.  
  36.     -- Lennart Augustsson
  37. [This signature is intentionally left blank.]
  38.