在Haskell中管理有状态计算系统

Question

所以,我有一个链接在一起的有状态处理器系统.例如,处理器可能会输出其最后10个输入的平均值.它要求州计算这个平均值.

我想向系统提交值,并获得输出.我也想在过去的任何时候跳回来恢复状态.IE浏览器.我通过系统运行1000个值.现在,我希望将系统"移动"回到我发送第500个值之后的状态.然后我想再次从那一点"重播"系统.

我还需要能够将历史状态保存到磁盘,这样我可以在将来的某个时间再次恢复整个事情(并且仍然可以使用后退和重放功能).当然,我需要用千兆字节的数据来做这件事,并且速度非常快:)

我一直在使用闭合来保持状态.但我想知道使用monad是否更有意义.我只读了3或4个monad的类比,所以还不太了解它们,所以请随时教育我.

如果每个处理器在monad中修改其状态,以保持其历史记录并且它与每个处理步骤的id相关联.然后以某种方式monad能够将其状态切换到过去的步骤id并在该状态下使用monad运行系统.monad将有一些机制(de)序列化自己的存储.

(并且考虑到数据的大小......它实际上甚至不应该都在内存中,这意味着monad需要映射到磁盘,缓存等...)

是否有现成的图书馆/机制/方法/概念已经完成或协助完成我正在尝试做的事情？

Answer 1

所以,我有一个链接在一起的有状态处理器系统.例如,处理器可能会输出其最后10个输入的平均值.它要求州计算这个平均值.

首先,它听起来像你所拥有的不只是"有状态处理器",而是像有限状态机和/或传感器.这可能是开始研究的好地方.

我想向系统提交值,并获得输出.我也想在过去的任何时候跳回来恢复状态.IE浏览器.我通过系统运行1000个值.现在,我希望将系统"移动"回到我发送第500个值之后的状态.然后我想再次从那一点"重播"系统.

当然,最简单的方法是简单地记录所有先前的状态.但是,由于听起来您拥有大量数据,因此所需的存储容易变得过高.我建议考虑如何以一种可以避免这种情况的方式构建处理器,例如:

• 如果处理器的状态可以在几步之前从其邻居的状态轻松地重建,则可以避免直接记录它
• 如果处理器在某些情况下很容易逆转,则无需立即记录; 可以直接计算倒带,并且可以作为定期快照完成日志记录
• 如果您可以将处理器固定到极少数状态,请确保这样做.
• 如果处理器在某些类型的输入上以非常可预测的方式运行,您可以将其记录下来 - 例如,如果它在某个截止值以下的数字输入上空闲,而不是记录每个值,只记录"空闲N步".

我还需要能够将历史状态保存到磁盘,这样我可以在将来的某个时间再次恢复整个事情(并且仍然可以使用后退和重放功能).当然,我需要用千兆字节的数据来做这件事,并且速度非常快:)

明确的状态是你的朋友.函数是表示活动状态机的便捷方式,但它们不能以任何简单的方式序列化.您希望将(基本上静态的)处理器网络与每个处理器用于计算下一步的一系列内部状态清晰分离.

是否有现成的库/机制/方法/概念已经完成,以完成我正在尝试做的事情？monad方法是否有意义？还有其他更好/特殊的方法可以帮助它有效地实现这一点,特别是考虑到我必须管理的大量数据吗？

如果你的大多数处理器都像有限状态传感器,你需要有各种类型的输入并产生不同类型的输出的处理器,你可能想要的实际上是基于Arrows 的结构,它为你提供了抽象的东西在某种意义上构成"类似功能",例如,将一个处理器的输入连接到另一个处理器的输出.

此外,只要您避开ArrowApply类并确保您的状态机模型仅返回输出值和新状态,您将保证避免隐式状态,因为(与函数不同)Arrows不会自动更高阶.

鉴于数据的大小...它甚至不应该都在内存中,这意味着monad需要映射到磁盘,缓存等...

给定处理器网络的静态表示,提供可读取数据,序列化/反序列化状态以及写入任何输出的增量输入/输出系统应该不会太困难.

作为一个快速,粗略的起点,这里有一个可能是我上面概述的最简单版本的例子,暂时忽略了日志记录问题:

data Transducer s a b = Transducer { curState :: s
                                   , runStep  :: s -> a -> (s, b)
                                   }

runTransducer :: Transducer s a b -> [a] -> [b]
runTransducer t [] = (t, [])
runTransducer t (x:xs) = let (s, y) = runStep t (curState t) x
                             (t', ys) = runTransducer (t { curState = s }) xs
                         in (t', y:ys)

它是一个简单的通用处理器,具有明确的内部状态,类型s输入和类型a输出b.该runTransducer函数推送输入列表,手动更新状态值,并收集输出列表.

PS - 因为你问的是monad,你可能想知道我给出的例子是否是一个.事实上,它是多个常见monad的组合,但哪些取决于你如何看待它.但是,我故意避免将它视为monad!问题是,monads只捕获在某种意义上非常强大的抽象,但同样的功能也使它们在某些方面对优化和静态分析更具抵抗力.需要排除的主要问题是处理器将其他处理器作为输入并运行它们(正如您可以想象的那样)可以创建几乎不可能分析的复杂逻辑.

因此,虽然处理器可能可能是monad,并且在某种逻辑意义上本质上是,但假装它们不是更有用; 施加人为限制以使静态分析更简单.