Haskell/Understanding monads/Solutions/State

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Example: Rolling dice[edit]

1.

rollNDiceIO :: Int -> IO [Int]
rollNDiceIO n = replicateM n (randomRIO (1, 6))

Dice without IO[edit]

1.

rollDice :: StdGen -> ((Int, Int), StdGen)
rollDice g = ((n, m), g'')
    where
    (n, g')  = randomR (1, 6) g
    (m, g'') = randomR (1, 6) g'

Dice and state[edit]

1.

-- A long version that matches the implementation of the previously shown rollDice function
rollNDice :: Int -> State StdGen [Int]
rollNDice n | n <= 0    = return []
rollNDice n = do
  generator <- get
  let (val, newGen) = randomR (1,6) generator
  put newGen
  vals <- rollNDice (n-1)
  return (val:vals)

-- A much more concise version of the solution
rollNDice :: Int -> State StdGen [Int]
rollNDice n = replicateM n rollDie
  where rollDie = state $ randomR (1, 6)

2.

-- For any monad, fmap = liftM = \f m -> m >>= return . f
-- In our case, we have:
fmap f pr = pr >>= return . f
-- Expanding (>>=):
fmap f pr = state $ \ st ->
    let (x, st') = runState pr st
    in runState ((return . f) x) st'
fmap f pr = state $ \ st ->
    let (x, st') = runState pr st
    in runState (return (f x)) st'
-- Expanding return:
fmap f pr = state $ \ st ->
    let (x, st') = runState pr st
    in runState ((\ y -> state $ (\z -> (y, z))) (f x)) st'
fmap f pr = state $ \ st ->
    let (x, st') = runState pr st
    in runState (state $ (\z -> (f x, z))) st'
-- runState and state undo each other:
fmap f pr = state $ \ st ->
    let (x, st') = runState pr st
    in (\z -> (f x, z)) st'
fmap f pr = state $ \ st ->
    let (x, st') = runState pr st
    in (f x, st')

-- Therefore:
instance Functor (State s) where
    fmap f pr = state $ \ st ->
       let (x, st') = runState pr st
       in (f x, st')

-- Alternatively, using the following helper function:
first f (x, y) = (f x, y)

fmap f pr = state $ \ st -> first f (runState pr st)
fmap f pr = state $ first f . runState pr

instance Functor (State s) where
    fmap f pr = state $ first f . runState pr

fmap f pr produces a state processor which runs pr and then applies f to the result pr gives back.

Note that, literally speaking, there is no value of type a inside State s a, as the latter is essentially just a function. Still, we can, through function composition, write an fmap instance which operates on the a values that will be produced by the state processor.

3.

modify :: (s -> s) -> State s ()
modify f = state $ \ st -> ((), f st)

gets :: (s -> a) -> State s a
gets f = state $ \ st -> (f st, st)

-- Alternatively, using get and put:
modify f = get >>= \ st -> put (f st)

gets f = get >>= \ st -> return (f st)
-- Or simply (compare with exercise 2):
gets f = fmap f get