Haskell中现有的大小惰性向量类型

Question

我希望能够使用O(1)摊销寻址与一个矢量类型，懒散地增长，根据要求的指数。

这可以通过使用mvector（PrimState m）a:与primref m[a]进行配对来保持剩余部分，并使用用于分期O(1)访问的标准加倍算法来实现：

{-# LANGUAGE ExistentialQuantification #-}
module LazyVec where

import Control.Monad.Primitive
import Data.PrimRef
import Data.Vector.Mutable (MVector)
import qualified Data.Vector.Mutable as M
import Data.Vector (fromList, thaw)
import Control.Monad (forM_)

data LazyVec m a = PrimMonad m => LazyVec (MVector (PrimState m) a) (PrimRef m [a])

-- prime the LazyVec with the first n elements
lazyFromListN :: PrimMonad m => Int -> [a] -> m (LazyVec m a)
lazyFromListN n xs = do
  let (as,bs) = splitAt n xs
  mvec <- thaw $ fromList as
  mref <- newPrimRef bs
  return $ LazyVec mvec mref

-- look up the i'th element
lazyIndex :: PrimMonad m => Int -> LazyVec m a -> m a
lazyIndex i lv@(LazyVec mvec mref) | i < 0     = error "negative index"
                                   | i < n     = M.read mvec i
                                   | otherwise = do
    xs <- readPrimRef mref
    if null xs
      then error "index out of range"
      else do
        -- expand the mvec by some power of 2
        -- so that it includes the i'th index
        -- or ends
        let n' = n * 2 ^ ( 1 +  floor (logBase 2 (toEnum (i `div` n))))
        let growth = n' - n
        let (as, bs) = splitAt growth xs
        M.grow mvec $ if null bs then length as else growth
        forM_ (zip [n,n+1..] as) . uncurry $ M.write mvec
        writePrimRef mref bs
        lazyIndex i lv
  where n = M.length mvec

我可以只使用我的代码--但我更愿意重用别人的（比如，我还没有测试过我的代码）。

在某些包中是否存在具有这些语义的向量类型（从一个可能无限的列表中懒散地创建、O(1)分期访问）？

Answer 1

正如Jake McArthur在评论中指出的：“如果它只是一个函数，那么我建议只使用现有的备忘录包之一，比如MemoTrie或data-memocombinators。它们应该会让它变得容易。”