How to do puremt in a monad using random-fu package

Question

So I'm writing a roguelike and I need to generate some dungeons randomly. I could use system.random but I really want to make it pure. I want to use newPureMT to generate a mersenne twister random source, then pass it into some monad transformers like stateT and readerT and a few others. So that I would end up with something along the lines of:

genDungeon = do
  x <- getRandomNumbers
  genrooms x
  y <- getRandomNumbers
  gendoors x
  etc

I can't figure out how to do this without staying in the IO monad. For example, it gives this example:

sample (uniform 1 100) :: State PureMT Int

Which means I should be able to:

blah = do
  x <- newPureMT
  runState genDungeon x

But even typing it into ghci yields the error

Overlapping instances for Data.Random.Lift.Lift
                            Data.Functor.Identity.Identity
                            (StateT PureMT Data.Functor.Identity.Identity)
  arising from a use of `sample' at <interactive>:1:0-28
Matching instances:
  instance [incoherent] (Monad m, MonadTrans t) =>
                        Data.Random.Lift.Lift m (t m)
    -- Defined in Data.Random.Lift
  instance [incoherent] (Monad m) =>
                        Data.Random.Lift.Lift Data.Functor.Identity.Identity m
    -- Defined in Data.Random.Lift

to which I have absolutely no idea what that means or how to fix it.

I've spent a few days trying to figure this out, and I'm just completly clueless. It is pretty obvious that there are some pretty heavy type signatures and lifting of some stuff that I have to apply to get stuff to work, but I cannot figure out what they are or how to do it.

Edit: Okay, so I was looking through the Mersenne Twister code and I saw that PureMT is an instance of randomgen which means that I can pass it into system.random and get pure code out of it, rendering random-fu unecessary. I still kind of wish I could figure out how to make this code work as random-fu gives you a ton of extra abilities like different random distributions, but his will do for my project.

Edit: Okay, so I ended up with this code:

rand :: (RandomGen g, MonadState g m) => Int -> Int -> m Int
rand lo hi = do
    r <- get
    let (val, r') = randomR (lo, hi) r
    put r'
    return val


gendungeons = replicateM 10 $ do
  x <- rand 0 24
  y <- rand 4 10
  z <- replicateM 10 $ rand 5 50
  let dungeon = makeadungeonpurelywiththeserandomvalues x y z
  return dungeon


test = do
  x <- newPureMT
  let dungeons = runState gendungeons x
  return dungeons

This pretty much allows me to do what I wanted syntactically, and it uses mersenne twister so it should be a heck of a lot faster. The only thing that bothers me is that on every single number generation, it will update the seed in the state monad and I have heard that it is really slow, although I don't know why. But this should be enough for my purposes.

You can certainly use `System.Random` in a pure fashion (see [this answer](http://stackoverflow.com/questions/2110535/sampling-sequences-of-random-numbers-in-haskell/2125329#2125329), for example). — Travis Brown, Nov 28 '10 at 08:41
You should add some type signatures to your functions so we have a better understanding of what's going on. Also runState returns a pure value of type (s,a) you can't end a "do" expression like that, if it's a pure value it's need to be lifted with return. — snk_kid, Nov 28 '10 at 11:33
runStateT is for monad transformers, runState is for plain state monad. — snk_kid, Nov 28 '10 at 11:42
@onmach: The guide to formatting is in a box on the right-hand-side of the page when you're asking or editing a question, with a link to [this more detailed page](http://stackoverflow.com/editing-help); said page is also accessible from the `?` button when you're asking a question. The buttons along the top of the text field in those situations also do formatting (by inserting the relevant characters). I took the liberty of fixing up the formatting in your question (code is indented with four spaces). — Antal Spector-Zabusky, Nov 28 '10 at 15:20
I noticed the markup stuff, but it isn't clickable for me. It is probably noscript or something, I'll work it out before I do another post. — David McHealy, Nov 28 '10 at 17:58
@onmach: This is very unlikely to be any kind of bottleneck, even using plain old `State StdGen`. Optimizing in advance because of something you read somewhere is a recipe for pain. — Travis Brown, Nov 28 '10 at 21:51

score 1 · Answer 1 · answered Nov 28 '10 at 09:31

For something like this I'd recommend using the Gen monad from QuickCheck. Its designed for creating random data structures, so you need to define your dungeon as a data structure and then write an "Arbitrary" instance for it (see the QuickCheck docs).

Your thinking seems to be along the lines of "get some random numbers and then transform them into a dungeon". A better way of thinking is "generate some random dungeon elements and connect them together randomly".

snk_kid · Accepted Answer · 2010-11-28T11:12:20.397

1

I wont say this is a better answer than Paul Johnson but this is one way to do it if I understood what you wanted:

import Control.Monad.State
import System.Random

-- utility function to hide plumbing of random generator types.
rand :: (Random a, RandomGen g, MonadState g m) => a -> a -> m a
rand lo hi = do
    r <- get
    let (val, r') = randomR (lo, hi) r
    put r'
    return val

(flip runState) (mkStdGen seed) $ do
    x <- rand 0 24
    y <- rand 4 10
    z <- rand 5 50
    ...
    ...

I'm using the standard random generator module since I've never used random-fu but the principle should be the same just make a rand action if it doesn't exist in the library.

I'm using type-classes to keep the code generic, you can use this with any monad (transformer) that is an instance of the MonadState type-class. You don't have to use type-classes you can use your specific monad in the type of rand instead if you want.

edited Nov 28 '10 at 11:12

answered Nov 28 '10 at 10:43

snk_kid

3,457
3
23
18

The reason why I wanted to use pureMT is that I heard somewhere that trying to use the normal random functions in haskell in the state monad slows things down a lot. Not just that the normal system random is something like 100x slower than mersenne twister, but also mutating the lazy state for every number generation is supposedly really slow. I was really hoping to figure out how it would be done in random-fu, because it looks like it was designed for this problem. – David McHealy Nov 28 '10 at 18:00
@onmach I'm not saying you should or shouldn't use either, I'm just saying I don't know anything about random-fu package but I'm guessing they probably have an action like this already and if not then you should be able to write you own to get the same sort of behaviour you want. I did have a very brief look at the docs, I saw that PureMT has a pure function which takes a seed like mkStdGen (don't remember the name for PureMT now). I read your edits just now, just looking at the docs now it says PureMT implements MonadRandom which you might be able to use instead of RandomGen. – snk_kid Nov 28 '10 at 20:22
@onmach I think you want the funciton getRandomPrimFromMTState, check the docs in Data.Random.Source.PureMT module. – snk_kid Nov 28 '10 at 20:26
I think you are right snk_kid. I'm not sure how I missed that part of the docs. Both that function and the one above it look promising for creating a MonadRandom. I'll have to give it a try sometime, but for now I'm going to go back to making my game. – David McHealy Nov 28 '10 at 22:22

How to do puremt in a monad using random-fu package

2 Answers2