[Haskell-cafe] In relation to shuffling
Alastair Reid
alastair at reid-consulting-uk.ltd.uk
Thu Jul 8 18:44:38 EDT 2004
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
More information about the Haskell-Cafe
mailing list