1

I would like to generate random sequences from a Markov chain. To generate the Markov chain I use the following code.

module Main where

import qualified Control.Monad.Random as R
import qualified Data.List as L
import qualified Data.Map as M

type TransitionMap = M.Map (String, String) Int
type MarkovChain = M.Map String [(String, Int)]

addTransition :: (String, String) -> TransitionMap -> TransitionMap
addTransition k = M.insertWith (+) k 1

fromTransitionMap :: TransitionMap -> MarkovChain
fromTransitionMap m =
  M.fromList [(k, frequencies k) | k <- ks]
  where ks = L.nub $ map fst $ M.keys m
        frequencies a = map reduce $ filter (outboundFor a) $ M.toList m
        outboundFor a k = fst (fst k) == a
        reduce e = (snd (fst e), snd e)

After collecting the statistics and generating a Markov Chain object I would like to generate random sequences. I could imagine this method could look something like that (pseudo-code)

generateSequence mc s
  | s == "." = s
  | otherwise = s ++ " " ++ generateSequence mc s'
  where s' = drawRandomlyFrom $ R.fromList $ mc ! s

I would greatly appreciate if someone could explain to me, how I should implement this function.

Edit

If anyone's interested it wasn't as difficult as I thought.

module Main where

import qualified Control.Monad.Random as R
import qualified Data.List as L
import qualified Data.Map as M

type TransitionMap = M.Map (String, String) Rational
type MarkovChain = M.Map String [(String, Rational)]

addTransition :: TransitionMap -> (String, String) -> TransitionMap
addTransition m k = M.insertWith (+) k 1 m

fromTransitionMap :: TransitionMap -> MarkovChain
fromTransitionMap m =
  M.fromList [(k, frequencies k) | k <- ks]
  where ks = L.nub $ map fst $ M.keys m
        frequencies a = map reduce $ filter (outboundFor a) $ M.toList m
        outboundFor a k = fst (fst k) == a
        reduce e = (snd (fst e), snd e)

generateSequence :: (R.MonadRandom m) => MarkovChain -> String -> m String
generateSequence m s
  | not (null s) && last s == '.' = return s
  | otherwise = do
                s' <- R.fromList $ m M.! s
                ss <- generateSequence m s'
                return $ if null s then ss else s ++ " " ++ ss

fromSample :: [String] -> MarkovChain
fromSample ss = fromTransitionMap $ foldl addTransition M.empty $ concatMap pairs ss
  where pairs s = let ws = words s in zipWith (,) ("":ws) ws

sample :: [String]
sample = [ "I am a monster."
         , "I am a rock star."
         , "I want to go to Hawaii."
         , "I want to eat a hamburger."
         , "I have a really big headache."
         , "Haskell  is a fun language."
         , "Go eat a big hamburger."
         , "Markov chains are fun to use."
         ]

main = do
  s <- generateSequence (fromSample sample) ""
  print s

The only tiny annoyance is the fake "" starting node.

2
  • 1
    if generateSequence is to be run in MonadRandom, you'd need returns there. Commented Aug 13, 2014 at 12:58
  • do you care to elaborate please? I'm not that experiences in the whole monad thing. I do understand enough, to see that ++ not gonna work if I try to concatenate a String and Monad m => m a. Second I'm not sure how drawRandomlyFrom function should look like
    – vasily
    Commented Aug 13, 2014 at 15:06

2 Answers 2

1

Not sure if this is what you're looking for. This compiles though:

generateSequence :: (R.MonadRandom m) => MarkovChain -> String -> m String
generateSequence mc s  | s == "." = return s
                       | otherwise = do  
                            s' <- R.fromList $ rationalize (mc M.! s)
                            s'' <- generateSequence mc s'
                            return $ s ++ " " ++ s'' 

rationalize :: [(String,Int)] -> [(String,Rational)]
rationalize = map  (\(x,i) -> (x, toRational i))
0
1

All random number generation needs to happen in either the Random monad or the IO monad. For your purpose, it's probably easiest to understand how to do that in the IO monad, using evalRandIO. In the example below, getRandom is the function we want to use. Now getRandom operates in the Random monad, but we can use evalRandIO to lift it to the IO monad, like this:

main :: IO ()
main = do
  x <- evalRandIO getRandom :: IO Double
  putStrLn $ "Your random number is " ++ show x

Note: The reason we have to add the type signature to the line that binds x is because in this particular example there are no other hints to tell the compiler what type we want x to be. However, if we used x in some way that makes it clear that we want it to be a Double (e.g., multiplying by another Double), then the type signature wouldn't be necessary.

Using your MarkovChain type, for a current state you can trivially get the available transitions in the form [(nextState,probability)]. (I'm using the word "probability" loosely, it doesn't need to be a true probability; any numeric weight is fine). This is what fromList in Control.Monad.Random is designed for. Again, it operates in the Random monad, but we can use evalRandIO to lift it to the IO monad. Suppose transitions is your list of transitions, having the type [(nextState,probability)]. Then, in the IO monad you can call:

nextState <- evalRandIO $ fromList transitions

You might instead want to create your own function that operates in the Random monad, like this:

getRandomTransition :: RandomGen g => MarkovChain -> String -> Rand g String
getRandomTransition currState chain = do
    let transitions = lookup currState chain
    fromList transitions

Then you can call this function in the IO monad using evalRandIO, e.g.

nextState <- evalRandIO $ getRandomTransition chain

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.