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

Question

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

我想向系统提交值，并获得输出。我也想跳回去，随时恢复过去的状态。 IE。我通过系统运行 1000 个值。现在，我想将系统“移动”回与发送第 500 个值后完全相同的状态。然后我想再次从那时起“重播”系统。

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

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

如果每个处理器修改其在 monad 中的状态，使其历史得以保留，并且每个处理步骤都与一个 id 相关联。然后不知何故，monad 能够将其状态切换到过去的步骤 id，并在该状态下运行 monad 的系统。并且 monad 将具有某种机制来(反)序列化自身以进行存储。

(考虑到数据的大小......它甚至不应该全部都在内存中，这意味着 monad 需要映射到磁盘、缓存等......)

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

Answer 1

So, I have a system of stateful processors that are chained together. For example, a processor might output the average of its last 10 inputs. It requires state to calculate this average.

首先，听起来你所拥有的不仅仅是“有状态的处理器”，而是像 finite-state machines 这样的东西。和/或 transducers .这可能是开始研究的好地方。

I would like to submit values to the system, and get the outputs. I also would like to jump back and restore the state at any time in the past. Ie. I run 1000 values through the system. Now I want to "move" the system back to exactly as it was after I had sent the 500th value through. Then I want to "replay" the system from that point again.

当然，这里最简单的方法是简单地保留所有先前状态的日志。但是，由于听起来您拥有大量数据，因此所需的存储空间很容易变得令人望而却步。我建议您考虑如何以可以避免这种情况的方式构建处理器，例如:

如果一个处理器的状态可以很容易地从它的邻居的状态重建几个步骤之前，你可以避免直接记录它

如果处理器在某些情况下很容易可逆，则无需立即记录；可以直接计算倒带，并且可以将日志记录为定期快照

如果您可以将处理器确定为非常少的状态，请确保这样做。

如果处理器在某些类型的输入上以非常可预测的方式运行，您可以这样记录 - 例如，如果它在低于某个截止值的数字输入上空闲，而不是记录每个值，只记录“空闲 N 步”。

I also need to be able to persist the historical state to disk so I can restore the whole thing again some time in the future (and still have the move back and replay functions work). And of course, I need to do this with gigabytes of data, and have it be extremely fast :)

显式状态是你的 friend 。函数是表示事件状态机的一种方便方式，但它们不能以任何简单的方式进行序列化。您希望将处理器(基本上是静态的)网络与每个处理器用于计算下一步的一系列内部状态完全分离。

Is there an existing library/mechanism/approach/concept that has already been done to accomplish what I'm trying to do? Does the monad approach make sense? Are there other better/special approaches that would help it do this efficiently especially given the enormous amount of data I have to manage?

如果您的大多数处理器都类似于有限状态转换器，并且您需要有接受各种类型输入并产生不同类型输出的处理器，那么您可能想要的实际上是 something with a structure based on Arrow s。 ，它为您提供了在某种意义上组成“类似函数”的事物的抽象，例如，将一个处理器的输入连接到另一个处理器的输出。

此外，只要您避免使用 ArrowApply类并确保您的状态机模型只返回一个输出值和一个新状态，您将保证避免隐式状态，因为(与函数不同)Arrow s 不会自动高阶。

Given the size of the data... it really shouldn't even all be in memory, which would mean the monad would need to be mapped to disk, cached, etc...

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

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

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函数推送输入列表，手动更新状态值，并收集输出列表。

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

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