Best way to generate a list with state (Haskell)

2
votes

Let's say I want to generate a list of items, while keeping track of some state. For example, generate [1..], while keeping track of the items generated so far, or generate a list of random numbers, keeping track of the RNG state.

It seems that there are two ways of doing this:

1) Generate a list of State Monads, [State s a], then run sequence to get a State s [a]. Then use runState to get the [a].

2) Use Monad transformers somehow.

What's a good example of the monad transformers way? Which is more idiomatic? What's the pros and cons of each?

2
haskellmonadsmonad-transformersstate-monad
A monad transformer is just a type which takes some other monad as a parameter and acts to add some other monadic effect to that original monad. You never need to touch transformers to do what you want to do. If you need to keep track of state, you use State; using a monad transformer does not mean that you must or cannot use State. There is already a package which precisely uses State to encapsulate the concept of generating random numbers purely. – user2407038
This is exactly what pipes and conduits are for. – Tom Ellis

2 Answers

4
votes

I've had to do quite a bit of this lately and I've found that [State s a] and sequence is the best option. I can't think of a useful/simple way of doing this with Monad Transformers. Even though list is a Monad, using sequence means we don't have to worry about a Monad inside a Monad.

I've had to use MaybeT for creating a Maybe Rand, but never for lists and states. Though I've only been doing Haskell for a couple of months, so there are probably other people who can answer with more experience behind them.

However - it's not always about finding a way to use Monads. Sometimes I've found that it's easier not to use a Monad but instead use some of the higher order functions that come with Data.List.

Here are some ways of carrying forward a value with lists that doesn't involve the state Monad (as input into GHCi):

> :t scanl
scanl :: (a -> b -> a) -> a -> [b] -> [a]
> scanl (+) 0 [1,2,3,4,5]
[0,1,3,6,10,15]

> :t mapAccumL
mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
> mapAccumL (\acc x -> (x+acc,x*2)) 0 [1,2,3,4,5]
(15,[2,4,6,8,10])

> :t unfoldr
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
> take 20 . unfoldr (\g -> Just $ randomR (0,10) g) $ mkStdGen 444
[2,3,8,0,7,5,2,10,10,5,10,2,4,2,8,9,1,1,5,10]

NB. you must import Data.List for scanl, mapAccumL and unfoldr

When working with Random numbers sometimes it's easier to generate a list of random numbers that we need rather than create a [Rand StdGen Int] list. For example this function which generates a random sized list of random numbers using applicatives:

> :t runRand
runRand :: RandomGen g => Rand g a -> g -> (a, g)
> fst . flip runRand (mkStdGen 12345) $ take <$> getRandomR (10,15) <*> getRandomRs (10,20) :: [Int]
[17,16,16,19,16,17,15,12,10,11,11,10,17,12,13]
4
votes

Your examples are quite orthogonal to the difference between StateT and State.

If we were to generate four random numbers using State, like this

import System.Random
import Control.Monad.State

rs :: State StdGen Int
rs = do
  (r,g) <- random `fmap` get
  put g
  return (r :: Int)

main = getStdGen >>= \g -> mapM_ print . flip evalState g . replicateM 4 $ rs

We ran the State action four times, collected the result in a list and finally printed each number in the list. But what if, for some reason, we needed to do IO inside each action rather than after collecting the results? This is where transformers become relevant

import System.Random
import Control.Monad.State

rs' :: StateT StdGen IO Int
rs' = do
  (r,g) <- random `fmap` get
  put g
  liftIO $ print r
  return (r :: Int)

main = getStdGen >>= \g -> flip evalStateT g . replicateM_ 4 $ rs'

Note that while the final result can still be accessed, I'm discarding it by using replicateM_.

So it's not so much a question of different ways of solving this problem, but whether you need the "bigger hammer" in order to mix actions of different monads.