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

Question

我希望能够使用O(1)分摊的寻址,其矢量类型根据所需的索引而懒惰地增长.

这可以通过使用配对a MVector (PrimState m) a: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。它们应该会让这一切变得简单。”