Haskell中一个现有的大小 – 惰性向量types

我希望能够使用O（1）摊销寻址与vectortypes，根据所需的指数懒惰地增长。

这可以通过使用标准加倍algorithm来实现对O（1）访问进行配对，使用MVector (PrimState m) a ：和PrimRef m [a]来保持余数。

 {-# 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 ma = 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 ma) 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 ma -> ma 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 

而且我可以使用我的代码 – 但我宁愿重用别人的（一个，我没有testing我的）。

带有这些语义的向量types（从可能无限的列表中延迟创build，O（1）分期存取）是否存在于某个包中？

Answer 1

正如Jake McArthur在评论中指出的那样：“如果只是一个函数，那么我推荐使用像MemoTrie或data-memocombinators这样的现有的memoization包，它们应该很容易。