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,