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

Question

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

我希望将值提交到系统，并获得输出。我也想在过去的任何时候跳回并恢复状态。即。我在系统中运行1000个值。现在，我想要将系统“移回”到我发送第500个值之后的状态。然后我想从那个点再次“重放”系统。

我还需要能够将历史状态持久化到磁盘上，这样我就可以在将来的某个时候再次恢复整个事情(并且仍然可以使用move back和replay函数)。当然，我需要对千兆字节的数据执行此操作，并且速度极快:)

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

如果每个处理器以这样一种方式修改其在monad中的状态，即保留其历史并且将其绑定到每个处理步骤的id。然后，不知何故，单子能够将其状态切换到过去的步骤id，并在单子处于该状态的情况下运行系统。并且monad会有某种机制来(反)序列化自身以进行存储。

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

有没有现成的库/机制/方法/概念已经被用来完成或帮助完成我想要做的事情？

Answer 1

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

首先，听起来您拥有的不仅仅是“有状态处理器”，而是类似于finite-state machines和/或transducers的东西。这可能是一个很好的研究起点。

我希望将值提交到系统，并获得输出。我也想在过去的任何时候跳回并恢复状态。即。我在系统中运行1000个值。现在，我想要将系统“移回”到我发送第500个值之后的状态。然后我想从那个点再次“重放”系统。

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

• 如果一个处理器的状态可以很容易地从之前几个步骤的邻居的状态中重建，你可以避免直接记录它
• 如果一个处理器在某些情况下很容易可逆，你不需要立即记录这些；可以直接计算倒带，并且可以将日志记录为定期快照
• 如果您可以将处理器限制为非常少量的状态，请确保这样做。
• 如果处理器在某些类型的输入上以非常可预测的方式运行，您可以将其记录下来-例如，如果它在低于某个分界点的数值输入上空闲，而不是记录每个值，只记录“空闲了N步”。

我还需要能够将历史状态持久化到磁盘上，这样我就可以在将来的某个时候再次恢复整个事情(并且仍然可以使用move back和replay函数)。当然，我需要对千兆字节的数据执行此操作，并且速度极快:)

显式状态是你的朋友。函数是表示活动状态机的一种方便方法，但它们不能以任何简单的方式序列化。您需要将处理器网络(基本上是静态的)与每个处理器用来计算下一步的一系列内部状态完全分开。

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

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

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

考虑到数据的大小，

...它甚至不应该全部在内存中，这意味着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函数推送输入列表，手动更新状态值，并收集输出列表。

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

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