[Haskell-cafe] In relation to shuffling

[Alastair Reid]

On Thursday 08 July 2004 20:40, paolo veronelli wrote:
> Most of my imperative pieces of software find their answers by
> touching around in some space of solutions and my favourite
> approximation algorithms use random distributions.
>
> Is it haskell the wrong languages for those, as I'm obliged to
> code them inside Monads loosing the benefits of lazyness?

No, no reason to lose laziness.  First off, suppose your algorithm is a loop 
that needs one random number per iteration.  An obvious structure would be:

  loop :: Solution -> IO Solution
  loop old_solution = do
    a <- randomIO
    let new_solution = next a old_solution
    if goodEnough new_solution 
      then return new_solution 
      else loop new_solution

With this structure, the loop is strict and imperative but the 'next' function 
which improves the solution is pure, lazy code.  Except in trivial cases, the 
next function will be where all the action is so you still get most of the 
benefit of laziness.

We can do better though.  Using two functions in System.Random, it's easy to 
get an infinite list of random numbers:

  randomRsIO :: IO [Int]
  randomRsIO = do
    g <- getStdGen
    return (randoms g)

Let's rewrite the above code to use a list of random numbers and an initial 
solution to search for a better solution:

  genSolutions :: [Int] -> Solution -> [Solution]
  genSolutions (r:rs) s0 = s0 : genSolutions (next r s0)
  -- slightly more cryptic implementation using foldl and map possible
  -- and probably preferable

  findGoodSolution :: [Int] -> Solution -> Solution
  findGoodSolution rs s0 = head (dropWhile (not . goodEnough) solutions)
   where
    solutions = genSolutions rs s0

  main = do
    rs <- randomRsIO
    print (findGoodSolution rs initial_solution)


Hope this helps,

--
Alastair Reid