home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / lang / function / 1500 < prev    next >
Encoding:
Internet Message Format  |  1993-01-09  |  2.1 KB
  1. Path: sparky!uunet!pipex!warwick!uknet!mucs!m1!bevan
  2. From: bevan@cs.man.ac.uk (Stephen J Bevan)
  3. Newsgroups: comp.lang.functional
  4. Subject: Re: Random permutations, linear time, fully functional?
  5. Message-ID: <BEVAN.93Jan9181926@panda.cs.man.ac.uk>
  6. Date: 9 Jan 93 18:19:26 GMT
  7. References: <C0KG2y.HvE@dcs.ed.ac.uk>
  8. Sender: news@cs.man.ac.uk
  9. Organization: Department of Computer Science, University of Manchester
  10. Lines: 42
  11. In-reply-to: pdc@dcs.ed.ac.uk's message of 9 Jan 93 02:54:33 GMT
  12.  
  13. In article <C0KG2y.HvE@dcs.ed.ac.uk> pdc@dcs.ed.ac.uk (Paul Crowley) writes:
  14.  
  15.   [ how do you efficiently permute an array in a pure functional way? ]
  16.  
  17. Assuming that the types "Updatable_Array/Updatable_Array_Action" are
  18. provided in the implementation, then the following Haskell code might
  19. work for the the example problem.
  20.  
  21.  >rand_permute :: Array Int Int -> Updatable_Array Int Int -> Array Int Int
  22.  >rand_permute source = with_updatable_array b (initalise `and_then` permute)
  23.  >  where initialise = for_all inds init
  24.  >        permute    = for_all inds (\i -> swap i (source!i))
  25.  >        b          = bounds source
  26.  >        inds       = range b
  27.  >        init i     = store i i
  28.  
  29.  >swap :: Int -> Int -> Updatable_Array_Action Int Int ()
  30.  >swap i j =
  31.  >  fetch i       `giving`   \tmp ->
  32.  >  fetch j       `giving`   \new_i ->
  33.  >  store i new_i `and_then`
  34.  >  store j tmp
  35.  
  36. where the various implementation defined actions have the following
  37. signatures :- 
  38.  
  39.  >fetch :: (Ix a) => a -> Updatable_Array_Action a b b
  40.  >store :: (Ix a) => a -> b -> Updatable_Array_Action a b ()
  41.  >giving :: (Ix a) => Updatable_Array_Action a b c
  42.  >       -> (c -> Updatable_Array_Action a b d)
  43.  >       -> Updatable_Array_Action a b d
  44.  >and_then :: (Ix a) => Updatable_Array_Action a b c
  45.  >         -> Updatable_Array_Action a b d
  46.  >         -> Updatable_Array_Action a b d
  47.  >for_all :: (Ix a) => [a] -> (a -> Updatable_Array_Action a b c)
  48.  >                         -> Updatable_Array_Action a b c
  49.  >with_updatable_array :: (Ix a) -> (a, a)
  50.  >                     -> Updatable_Array_Action a b c -> Array a b
  51.  
  52. yours treading carefully,
  53.  
  54. bevan
  55.