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

1 Nov 2014

      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:

```
randSrc :: IORef StdGen
randSrc = unsafePerformIO $ newIORef =<< newStdGen
{-# NOINLINE randSrc #-}

getRand :: IO Int
getRand = atomicModifyIORef' randSrc (swap . next)

-- We can probably use the following function to avoid calling
-- `unsafePerformIO` whenever calling 'getRand`,
-- assuming some optimization flag enabled:
getRandUnsafe :: Int
getRandUnsafe = unsafePerformIO getRand
{-# NOINLINE getRandUnsafe #-}
{-# RULES "getRandUnsafe"
  getRandUnsafe = unsafePerformIO getRand
 #-}
```

But this hack seems rather dirty and unsafe.

Is there any workaround to achieve the same thing?

-- Hiromi ISHII
konn.jinro@gmail.com