The Haskell RNG and state

Question

As a Java person learning Haskell I was getting use to the new way of thinking about everything but I've spent half a day trying to implement something with a simple RNG and am getting nowhere. In Java I could crate a static RNG and call it with Classname.random.nextInt(10) and it would meet these criteria:

1. I wouldn't have to keep a reference to the RNG and I could call it ad-hoc (even from inside a loop or a recursive function)
2. It would produce a new random number every time it was called
3. It would produce a new set of random numbers every time the project executed

So far in Haskell I'm facing the classic programmers dilemma - I can have 2/3. I'm still learning and have absolutely no idea about Monads, except that they might be able to help me here.

My Most recent attempt has been this:

getRn :: (RandomGen g) => Int -> Int -> Rand g Int
getRn lo hi= getRandomR (lo,hi)

--EDIT: Trimming my questions so that it's not so long winded, replacing with a summary and then what I ended up doing instead:

After creating a bunch of random cities (for TSP), I maped over them with a function createEdges that took a city and connected it to the rest of the cities: M.mapWithKey (\x y -> (x,(createEdges y [1..3] makeCountry)))

PROBLEM:

I wanted to replace [1..3] with something random. I.e. I wanted to map randomness (IO) over pure code. This caused no end of confusion for me (see people's attempt to answer me below to get a good sense of my confusion). In fact I'm still not even sure if I'm explaining the problem correctly.

I was getting this type of error: Couldn't match expected type [Int] with actual type IO [Int]

SOLUTION:

So after finding out that what I wanted to do was fundamentally wrong in a functional environment, I decided to change my approach. Instead of generating a list of cities and then applying randomness to connect them, I instead created an [[Int]] where each inner list represented the random edges. Thereby creating my randomness at the start of the process, rather than trying to map randomness over the pure code.

(I posted the final result as my own answer, but SO won't let me accept my own answer yet. Once it does I've reached that threshold I'll come back and accept)

Answer 1

You can work with random numbers without any monads or IO at all if you like. All you have to know is, that as there is state (internal state of the random-number-generator) involved you have to take this state with you.

In my opinion the easiest framework for this is Sytem.Random.

Using this your getRn function could look like this:

getRn :: (RandomGen g) => Int -> Int -> g -> (Int, g)
getRn lo hi g = randomR (lo,hi) g

here you can view g as the state I mentioned above - you put it in and you get another back like this (in ghci):

> let init = mkStdGen 11
> let (myNr, nextGen) = getRn 1 6 init
> myNr
6
> let (myNr, nextGen') = getRn 1 6 nextGen
> myNr
4

I think you can start by using just this - thread the gen around and later when you get all the monad stuff come back and make it a bit easier to write/read.

I don't know the definitions of your data but here is a simple example that uses this technique:

module StackOQuestion where

import System.Random

getRn :: (RandomGen g) => Int -> Int -> g -> (Int, g)
getRn lo hi = randomR (lo,hi)

getRnList :: (RandomGen g) => (g -> (a, g)) -> Int -> g -> ([a], g)
getRnList f n g
  | n <= 0    = ([], g)
  | otherwise = let (ls, g') = getRnList f (n-1) g
                    (a, g'') = f g'
                in  (a:ls, g'')

type City = (Int, Int)

randomCity :: (RandomGen g) => g -> (City, g)
randomCity g =
    let (f, g')  = getRn 1 6 g
        (s, g'') = getRn 1 6 g'
    in  ((f, s), g'')

randomCities :: (RandomGen g) => (Int, Int) -> g -> ([City], g)
randomCities (minC, maxC) g = 
  let (count, g') = getRn minC maxC g 
  in getRnList randomCity count g'

and you can test it like this:

> let init = mkStdGen 23
> randomCities (2,6) init
([(4,3),(1,2)],394128088 652912057)

As you can see this creates two Cities (here simply represented as an integer-pair) - for other values of init you will get other answers.

If you look the right way at this you can see that there is already the beginning of a state-monad there (the g -> ('a, g) part) ;)

PS: mkStdGen is a bit like the Random-initialization you know from Java and co (the part where you usually put your system-clock's tick-count in) - I choose 11 because it was quick to type ;) - of course you will always get the same numbers if you stick with 11 - so you will need to initialize this with something from IO - but you can push this pack to main and keep pure otherwise if you just pass then g around

Answer 2

I would say if you want to work with random numbers, the easiest thing to do is to use an utility library like Control.Monad.Random.

The more educational, work intensive path is to learn to write your own monad like that. First you want to understand the State monad and get comfortable with it. I think studying this older question (disclaimer: I have an answer there) may be a good starting point for studying this. The next step I would take is to be able to write the State monad on my own.

After that, the next exercise I would try is to write a "utility" monad for random number generation. By "utility" monad what I mean is a monad that basically repackages the standard State monad with an API that makes it easier for that specific task. This is how that Control.Monad.Random package is implemented:

-- | A monad transformer which adds a random number generator to an
-- existing monad.
newtype RandT g m a = RandT (StateT g m a)

Their RandT monad is really just a newtype definition that reuses StateT and adds a few utility functions so that you can concentrate on using random numbers rather than on the state monad itself. So for this exercise, you basically design a random number generation monad with the API you'd like to have, then use the State and Random libraries to implement it.

Answer 3

Edit: After a lot more reading and some extra help from a friend, I finally reduced it to this solution. However I'll keep my original solution in the answer as well just in case the same approach helps another newbie like me (it was a vital part of my learning process as well).

-- Use a unique random generator (replace <$> newStdGen with mkStdGen 123 for testing)
generateTemplate = createCitiesWeighted <$> newStdGen

-- create random edges (with weight as pair) by taking a random sized sample of randoms
multiTakePair :: [Int] -> [Int] -> [Int] -> [[(Int,Int)]]
multiTakePair ws (l:ls) is = (zip chunka chunkb) : multiTakePair remaindera ls remainderb
    where
        (chunkb,remainderb) = splitAt l is
        (chunka,remaindera) = splitAt l ws

-- pure version of utilizing multitake by passing around an RNG using "split"
createCitiesWeighted :: StdGen -> [[(Int,Int)]]
createCitiesWeighted gen = take count result
    where
        (count,g1) = randomR (15,20) gen
        (g2,g3) = split g1
        cs = randomRs (0, count - 2) g1
        es = randomRs (3,7) g2
        ws = randomRs (1,10) g3
        result = multiTakePair ws es cs

The original solution -----

As well as @user2407038's insightful comments, my solution relied very heavily on what I read from these two questions:

• Sampling sequences of random numbers in Haskell
• Random Integer in Haskell

(NB. I was having an issue where I couldn't work out how to randomize how many edges each city would have, @AnrewC provided an awesome response that not only answered that question but massively reduce excess code)

module TspRandom (
    generateCityTemplate
) where

import Control.Monad (liftM, liftM2) -- promote a pure function to a monad


-- @AndrewC's suggestion
multiTake :: [Int] -> [Int] -> [[Int]]
multiTake (l:ls) is = chunk : multiTake ls remainder
    where (chunk,remainder) = splitAt l is

-- Create a list [[Int]] where each inner int is of a random size (3-7)
-- The values inside each inner list max out at 19 (total - 1)
createCities = liftM (take 20) $ liftM2 multiTake (getRandomRs (3,7)) (getRandomRs (0, 19))

-- Run the generator
generateCityTemplate = do
    putStrLn "Calculating # Cities"
    x <- createCities
    print x
    return ()

Answer 4

The state monad is actually very simple. It is just a function from a state to a value and a new state, or:

data State s a = State {getState :: s -> (s, a)}

In fact, this is exactly what the Rand monad is. It isn't necessary to understand the mechanics of State to use Rand. You shouldn't be evaluating the Rand inside of IO, just use it directly, using the same do notation you have been using for IO. do notation works for any monad.

createCities :: Rand StdGen Int 
createCities = getRn minCities maxCities

x :: Cities -> X
x = ...

func :: Rand StdGen X
func = do 
  cities <- createCities
  return (x cities)

-- also valid
func = cities <$> createCities
func = createCities >>= return . x

You can't write getConnections like you have written it. You must do the following:

getConnections :: City -> Country -> Rand StdGen [Int]
getConnections c country = do 
  edgeCount <- createEdgeCount 
  fromIndecies [] edgeCount (citiesExcludeSelf c country)

Any function which calls getConnections will have to also return a value of type Rand StdGen x. You can only get rid of it once you have written the entire algorithm and want to run it.

Then, you can run the result using evalRandIO func, or, if you want to test some algorithm and you want to give it the same inputs on every test, you can use evalRand func (mkStdGen 12345), where 12345, or any other number, is your seed value.