如何将有状态计算应用于列表？

Question

让我们想象一下大脑的一个虚拟子集：

+增加计数器

-减少计数器

一个简单的程序：

program = "++++--" -- should evaluate to 2

和一个有状态的评价功能：

eval :: Char -> State Int Char
eval '+' = do x <- get
              put (x + 1)
              return 'I'
eval '-' = do x <- get
              put (x - 1)
              return 'D'

你将如何评价这个项目？(在我看来，这是一种fold，但我无法将头绕过去，而且感觉这不是正确的方法.)

Answer 1

您可以使用来自traverse_的Data.Foldable

import Data.Foldable (traverse_)
execState (traverse_ eval "++++--") 0

Answer 2

您要寻找的函数是sequence，它具有签名sequence :: Monad m => [m a] -> m [a]，在处理State这样的单变量时，它是一个非常常见的模式。

对于您的代码，您希望评估器看起来如下所示：

evalBF :: String -> State Int String
evalBF = sequence . map eval

然后，您将对其进行全面评估，如下所示：

main :: IO ()
main = do
       src <- getLine
       print $ runState (evalBF src) 0

Answer 3

一个丑陋的解决方案，但使用折叠，你正确地怀疑是适用的。

import Control.Monad.Trans.State

program = "++++--"

eval :: Char -> State Int Char
eval '+' = do
    x <- get
    put (x + 1)
    return 'I'
eval '-' = do
    x <- get
    put (x - 1)
    return 'D'

evalList :: [Char] -> State Int Char
evalList = foldl (\s c -> (s >> eval c)) (return ' ')

main = putStrLn $ show $ runState (evalList program) 0