haskell - Haskell 中现有的尺寸惰性向量类型

Question

我希望能够将 O(1) 摊销寻址与根据所需索引懒惰增长的向量类型一起使用。

这可以通过使用配对 MVector (PrimState m) a 来实现。 :
与 PrimRef m [a]保留剩余部分，使用标准的加倍算法进行 amoritzed 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 。它们应该很容易。”