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

Hiromi ISHII konn.jinro at gmail.com
Sat Nov 1 09:25:17 UTC 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 at gmail.com



-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 496 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20141101/76d25372/attachment.sig>


More information about the Haskell-Cafe mailing list