🚀 go-pugleaf

In article <C0KG2y.HvE@dcs.ed.ac.uk> pdc@dcs.ed.ac.uk (Paul Crowley) writes:

  [ how do you efficiently permute an array in a pure functional way? ]

Assuming that the types "Updatable_Array/Updatable_Array_Action" are
provided in the implementation, then the following Haskell code might
work for the the example problem.

 >rand_permute :: Array Int Int -> Updatable_Array Int Int -> Array Int Int
 >rand_permute source = with_updatable_array b (initalise `and_then` permute)
 >  where initialise = for_all inds init
 >        permute    = for_all inds (\i -> swap i (source!i))
 >        b          = bounds source
 >        inds       = range b
 >        init i     = store i i

 >swap :: Int -> Int -> Updatable_Array_Action Int Int ()
 >swap i j =
 >  fetch i       `giving`   \tmp ->
 >  fetch j       `giving`   \new_i ->
 >  store i new_i `and_then`
 >  store j tmp

where the various implementation defined actions have the following
signatures :- 

 >fetch :: (Ix a) => a -> Updatable_Array_Action a b b
 >store :: (Ix a) => a -> b -> Updatable_Array_Action a b ()
 >giving :: (Ix a) => Updatable_Array_Action a b c
 >       -> (c -> Updatable_Array_Action a b d)
 >       -> Updatable_Array_Action a b d
 >and_then :: (Ix a) => Updatable_Array_Action a b c
 >         -> Updatable_Array_Action a b d
 >         -> Updatable_Array_Action a b d
 >for_all :: (Ix a) => [a] -> (a -> Updatable_Array_Action a b c)
 >                         -> Updatable_Array_Action a b c
 >with_updatable_array :: (Ix a) -> (a, a)
 >                     -> Updatable_Array_Action a b c -> Array a b

yours treading carefully,

bevan