Haskell中适配ST monad的最优可变队列数据结构选型问题

首先解答你提到的两个方案的疑问：

1. STRef包装普通列表的问题你已经明确，队尾操作O(n)的复杂度确实不适合绝大多数队列使用场景，无需考虑。
2. Data.Sequence本身是纯不可变数据结构，不管是否用STRef包装，它本身都不具备原地可变的特性。如果你用STRef存储Data.Sequence，每次修改本质是生成新的Sequence副本再更新STRef的指向，只是Sequence本身的入队、出队操作都是分摊O(1)复杂度，所以这个方案实际性能表现也不错。

最优选型推荐 #

方案1：原生可变ST队列（性能最优） #

直接使用专门为ST Monad设计的STQueue类型，来自stqueue包的Data.ST.Queue模块，是真正的原地可变FIFO队列，入队、出队、判空等所有核心操作都是O(1)时间复杂度，不需要自己手动封装STRef，使用示例：

import Control.Monad.ST
import Data.ST.Queue

demo :: ST s (Maybe Int)
demo = do
  -- 初始化空队列
  q <- newQueue
  -- 队尾入队
  enqueue q 1
  enqueue q 2
  -- 队首出队
  res <- dequeue q -- 得到Just 1
  dequeue q -- 得到Just 2
  dequeue q -- 得到Nothing
  return res

方案2：STRef + Data.Sequence（无额外依赖） #

如果你不想引入新的依赖，Data.Sequence属于绝大多数项目默认自带的containers包，搭配STRef使用完全可以满足需求，分摊O(1)的操作复杂度对于大多数场景足够用，使用示例：

import Control.Monad.ST
import Data.STRef
import Data.Sequence (Seq(..), (|>), viewl)
import qualified Data.Sequence as Seq

demo :: ST s (Maybe Int)
demo = do
  qRef <- newSTRef Seq.empty
  -- 入队
  modifySTRef qRef (|> 1)
  modifySTRef qRef (|> 2)
  -- 出队
  q <- readSTRef qRef
  case viewl q of
    x :< rest -> do
      writeSTRef qRef rest
      return $ Just x
    EmptyL -> return Nothing

选型建议 #

如果队列操作频率很高、对性能要求苛刻，优先选择原生STQueue方案；如果是轻量使用、不想增加额外依赖，STRef + Data.Sequence的方案完全可用。

内容的提问来源于stack exchange，提问作者Danish A. Alvi