Я бы хотел использовать 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 [email protected](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) амортизированный доступ?
