Une Taille Existante-Paresseux Type De Vecteur En Haskell

Question

J'aimerais être en mesure d'utiliser O(1) amorti adressage avec un type de vecteur qui pousse paresseusement selon l'exigeait l'index.

Cela pourrait être réalisé en utilisant un couplage MVector (PrimState m) a: avec un PrimRef m [a] pour tenir le reste, l'utilisation de la norme de doublement de l'algorithme pour amoritzed O(1) accès:

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

Et j'ai pu utiliser mon code mais je préfère la réutilisation de quelqu'un d'autre (pour l'un, je n'ai pas testé le mien).

Un type de vecteur avec ces sémantique (paresseux création d'un peut-être-liste infinie, O(1) amorti d'accès), il existe dans certains colis?

Answer 1

Comme Jake McArthur a noté dans les commentaires: "Si c'est juste une fonction, alors je recommande simplement à l'aide de l'un de ces memoization paquets comme MemoTrie ou de données-memocombinators. Ils devraient faire, c'est facile."