[Haskell-cafe] How to use randomized algorithm within the implementation of pure data structures?

[Bardur Arantsson]

On 2014-11-01 10:25, Hiromi ISHII wrote:
> Hi cafe,
> 
> I'm currently implementing the data structure representing algebraic numbers.
> 
> Implementing algebraic number arithmetic requires polynomial factorisation.
> Pure algorithm for factoring (Berlekamp's algorithm) is more expensive than
> the randomized one (Cantor-Zassenhaus algorithm) , so I want to use the
> latter algorithm.
> 
> Since C-Z algorithm is a randomized algorithm, we have to have an access
> for random number generator when calculating algebraic number arithmetics
> e.g. writing Num instance for algebraic numbers.
> 
> Here is the problem: how to pass-around random number generator throughout pure computaion?
> 
> I think one immediate solution is to create global state with `newStdGen` and `unsafePerformIO` like below:
> 

You can just use the State monad to thread the StdGen around and
"update" it when you need to. You can get a pure interface by hiding
away the runState behind a function:

  -- The is the function you export from your module.
  myAlgorithm :: StdGen -> ... -> ...
  myAlgorithm g .... = fst . runState (myAlgorithm' ...) g

  myAlgorithm' :: ... -> State StdGen Result
  myAlgorithm' ... = do
     ...
     x <- rand
     ...
     return $ ...

  rand :: State StdGen a
  rand = do
    x <- get
    (a, g') <- random    -- Here "random" is from System.Random
    put $! g'
    return a

(The above probably contains typos, and can probably also be prettified,
but hopefully you get the gist.)

Regards,