home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / lang / function / 1498 < prev    next >
Encoding:
Internet Message Format  |  1993-01-09  |  2.1 KB
  1. Path: sparky!uunet!think.com!enterpoop.mit.edu!mintaka.lcs.mit.edu!ai-lab!life.ai.mit.edu!tmb
  2. From: tmb@arolla.idiap.ch (Thomas M. Breuel)
  3. Newsgroups: comp.lang.functional
  4. Subject: Re: Random permutations, linear time, fully functional?
  5. Date: 9 Jan 93 14:06:20
  6. Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
  7.     Perceptive)
  8. Lines: 29
  9. Message-ID: <TMB.93Jan9140620@arolla.idiap.ch>
  10. References: <C0KG2y.HvE@dcs.ed.ac.uk>
  11. Reply-To: tmb@idiap.ch
  12. NNTP-Posting-Host: arolla.idiap.ch
  13. In-reply-to: pdc@dcs.ed.ac.uk's message of Sat, 9 Jan 1993 02:54:33 GMT
  14.  
  15. In article <C0KG2y.HvE@dcs.ed.ac.uk> pdc@dcs.ed.ac.uk (Paul Crowley) writes:
  16.  
  17.    Following a long and heated discussion on the topic in a local
  18.    newsgroup in which the local ML experts have come up hands empty
  19.    (surprising given this is Edinburgh), I'm looking for fully functional
  20.    ways of solving certain permutation problems which imperative languages
  21.    like C can solve in linear time.  In particular, I'd like to be able to
  22.    compose and invert permutations and generate random ones in linear
  23.    time.  If you don't like mixing "random" and "fully functional", you
  24.    could always ask for a list of random numbers as input. For example, an
  25.    equivalent of this C function would be the best part of a solution:
  26.  
  27. Use version arrays. They are an implementation of functional vectors,
  28. and the kind of update that happens in an imperative algorithm can be
  29. carried out in constant time. I think every functional language should
  30. provide them, either as the default implementation of a vector, or,
  31. at least, as another datatype. In SML, you can hack them yourself,
  32. except that the type signature will include some weak types that
  33. needn't be weak.
  34.  
  35. I doubt that you can do better than "n log n" if all you have is lists
  36. and functional vectors with update by copying.
  37.  
  38. In general, you don't need special ideas ("do it by sorting") in order
  39. to convert imperative algorithms to functional algorithms with a
  40. logarithmic overhead. Instead, simply use a balanced tree to represent
  41. arrays.  That will give you Theta(log n) time access and "update".
  42.  
  43.                     Thomas.
  44.