链接状态单子

Question

我有一个功能

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

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

如何运行step具有不同值的 s序列n使用上一步的状态和每个步骤？

所以例如步骤如下

第一步产生(16,1)，然后我想将其用作下一步n = 10应该产生的输入(6, 2)。将第一步中的 1 添加到其中，并将第一步中的 16 与新的 n 相加。

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

我知道使用 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

功能，

mapM step [25,10,5,1]

或更一般的

traverse step [25,10,5,1]

运行step在每个名单[25,10,5,1]。调用

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

在初始状态设置为 的情况下运行函数41，返回步骤输出列表和最终状态。

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

如果您想将状态与输出一起列出，只需修改step以包含它们。

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

或者，换一种方式

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

结果是， ([(16,1),(1,0),(0,0),(0,0)],0)仍然不是您要查找的内容，而是更接近。恐怕我不太了解你方程的细节，无法得到你正在寻找的东西，但这应该有助于理清 State 部分，让你专注于数学。

要实现上述go功能：

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

和

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

产量，

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

希望有帮助