Haskell中的现有尺寸

Haskell中的现有尺寸 - 延迟矢量类型(An Existing Size-Lazy Vector Type In Haskell)

我希望能够使用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）摊销访问）？

I'd like to be able to use O(1) amortized addressing with a vector type that grows lazily according to the demanded index.

This could be achieved by using pairing an MVector (PrimState m) a: with a PrimRef m [a] to hold the remainder, using the standard doubling-algorithm for amoritzed O(1) access:

{-# 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

And I could just use my code - but I'd rather reuse someone else's (for one, I haven't tested mine).

Does a vector type with these semantics (lazy creation from a possibly-infinite list, O(1) amortized access) exist in some package?

最满意答案

正如杰克·麦克阿瑟（Jake McArthur）在评论中指出：“如果这只是一个功能，那么我建议只使用MemoTrie或数据复制器之类的现有记忆软件包之一。

As Jake McArthur noted in the comments: "If it's just a function, then I recommend just using one of the existing memoization packages like MemoTrie or data-memocombinators. They should make it easy."