Chaining State Monad

Question

I have a function

step :: Int -> State Int Int
step n = get >>= \x ->  put  (x `div` n) >> return (x `mod` n)

λ> runState (step 25) 41
(16,1)

How do I run a sequence of steps, with different values of n and each step using the state from the last step?

so for example the steps would be as follows

step one yields (16,1) which I then want to use as input for my next step with n = 10 which should yield (6, 2). With the 1 from the first step being added to and the 16 in step one being mod with the new n.

n = 25 gives (16,1) then
n = 10 gives (6,2)  then
n = 5  gives (1,3) then
n = 1 gives (0,4)

I am aware that using State here might not be correct; but I am trying to use it as a way to learn.

may aim is to implement this function with the state monad.

greedy :: Double -> Int
greedy owed = snd $ foldl go (pennies,0) [25, 10, 5, 1]
  where
    pennies                     = floor . (*100) $ owed
    go (remaining,counter) coin = (remaining',counter')
      where
        remaining' = remaining `mod` coin
        counter'   = counter + remaining `div` coin

Answer 1

The function,

mapM step [25,10,5,1]

or the more general

traverse step [25,10,5,1]

runs step on each of the list of [25,10,5,1]. Invoking

runState  (mapM step [25,10,5,1]) 41

runs the function with the initial state set to 41, returning the list of step outputs and the final state.

([16,1,0,0],0)

If you want to list the states along with the output, just modify step to include them.

step n = get >>= \x ->  put  (x `div` n) >> return ((x `mod` n),(x `div` n))

or, put another way

step n = do 
  x <- get
  let (r,x') = (x `mod` n,x `div` n)
  put  x'
  return (r,x')

The result is, ([(16,1),(1,0),(0,0),(0,0)],0), still not what you are looking for, but closer. I'm afraid I don't understand the particulars of your equation well enough to get what you are looking for, but this should help sort out the State part, allowing you to focus on the math.

To make the above go function:

go n = do
   (r,c) <- get
   let (r',c') = (r `mod` n, c + (r `div` n))
   put (r',c')
   return (r',c')

and

runState (mapM go [25,10,5,1]) (41,0)

yields,

([(16,1),(6,2),(1,3),(0,4)],(0,4))

Hope that helps