亲爱的(est)堆栈交换器，
我目前正在实现一些需要访问“队列”(FIFO) 数据结构的算法。我正在使用 ST monad ，因此正在寻找与 ST monad 的“内存可变性”很好地互补的队列实现。在这一点上，我只是想在列表上使用 newSTRef (但是同样，访问最后一个元素是 O(n) 的复杂性，我想尽可能地避免这种情况。我也考虑过使用 Data.Sequence，但我不确定如果使用它是否真的是“可变的”在没有 newSTRef 初始化的 ST monad 中。
Stack Exchange 的好心人能否指导 Haskell 初学者在上述情况下最好的数据结构(或模块)是什么？
最佳答案
选项包括实现传统的 ring buffer在 STArray 之上，或使用由 STRef 构建的可变单链表，如:
type CellRef s a = STRef s (Cell s a)
data Cell s a = End | Cell a (CellRef s a)
data Q s a = Q { readHead, writeHead :: CellRef s a }
如果您想要Q 的轻松增长但又喜欢环形缓冲区的低指针开销，您可以通过让每个单元格都有一个STArray 来获得中间立场慢慢填满。当它满了，分配一个新的单元格；当从中读取清空它时，前进到下一个单元格。你明白了。
关于haskell - Haskell 中可用的最佳(可变)队列数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/69441612/