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

Question

让我们想象一个 Brainf*ck 的虚拟子集：

+ 递增计数器

- 递减计数器

一个简单的程序：

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

您正在寻找的函数是 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 2

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

import Data.Foldable (traverse_)
execState (traverse_ eval "++++--") 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

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

How to apply stateful computation to a list?

haskell

state-monad