vector-functorlazy (empty) → 0.0.1
raw patch · 5 files changed
+444/−0 lines, 5 filesdep +basedep +ghc-primdep +primitivesetup-changed
Dependencies added: base, ghc-prim, primitive, vector, vector-th-unbox
Files
- Setup.hs +2/−0
- src/Data/Vector/FunctorLazy.hs +210/−0
- src/Data/Vector/FunctorLazy/Common.hs +40/−0
- src/Data/Vector/FunctorLazy/Mutable.hs +161/−0
- vector-functorlazy.cabal +31/−0
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ src/Data/Vector/FunctorLazy.hs view
@@ -0,0 +1,210 @@+{-# LANGUAGE TemplateHaskell #-}+{-# LANGUAGE RankNTypes #-}+{-# LANGUAGE ScopedTypeVariables,TypeFamilies,FlexibleInstances,MultiParamTypeClasses #-}++-- | Functor-lazy vectors are like boxed vectors, but support mapping a function onto all elements in constant time. All vector operations (except slicing) are fully supported. See <http://github.com/mikeizbicki/functor-lazy> for more details.+module Data.Vector.FunctorLazy+ (+ -- * Functor-lazy vectors+ Vector, MVector,++ -- * Accessors++ -- ** Length information+ VG.length, VG.null,++ -- ** Indexing+ (VG.!), (VG.!?), VG.head, VG.last,+ VG.unsafeIndex, VG.unsafeHead, VG.unsafeLast,++ -- ** Monadic indexing+ VG.indexM, VG.headM, VG.lastM,+ VG.unsafeIndexM, VG.unsafeHeadM, VG.unsafeLastM,++-- -- ** Extracting subvectors (slicing)+-- slice, init, tail, take, drop, splitAt,+-- unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,++ -- * Construction++ -- ** Initialisation+ VG.empty, VG.singleton, VG.replicate, VG.generate, VG.iterateN,++ -- ** Monadic initialisation+ VG.replicateM, VG.generateM, VG.create,++ -- ** Unfolding+ VG.unfoldr, VG.unfoldrN,+ VG.constructN, VG.constructrN,++ -- ** Enumeration+ VG.enumFromN, VG.enumFromStepN, VG.enumFromTo, VG.enumFromThenTo,++ -- ** Concatenation+ VG.cons, VG.snoc, (VG.++), VG.concat,++ -- ** Restricting memory usage+ VG.force,++ -- * Modifying vectors++ -- ** Bulk updates+ (VG.//), VG.update, VG.update_,+ VG.unsafeUpd, VG.unsafeUpdate, VG.unsafeUpdate_,++ -- ** Accumulations+ VG.accum, VG.accumulate, VG.accumulate_,+ VG.unsafeAccum, VG.unsafeAccumulate, VG.unsafeAccumulate_,++ -- ** Permutations + VG.reverse, VG.backpermute, VG.unsafeBackpermute,++ -- ** Safe destructive updates+ VG.modify,++ -- * Elementwise operations++ -- ** Indexing+ VG.indexed,++-- -- ** Mapping+-- map, imap, concatMap,++-- -- ** Monadic mapping+-- mapM, mapM_, forM, forM_,++ -- ** Zipping+ VG.zipWith, VG.zipWith3, VG.zipWith4, VG.zipWith5, VG.zipWith6,+ VG.izipWith, VG.izipWith3, VG.izipWith4, VG.izipWith5, VG.izipWith6,+ VG.zip, VG.zip3, VG.zip4, VG.zip5, VG.zip6,++ -- ** Monadic zipping+ VG.zipWithM, VG.zipWithM_,++ -- ** Unzipping+ VG.unzip, VG.unzip3, VG.unzip4, VG.unzip5, VG.unzip6,++ -- * Working with predicates++ -- ** Filtering+ VG.filter, VG.ifilter, VG.filterM,+ VG.takeWhile, VG.dropWhile,++-- -- ** Partitioning+-- VG.partition, VG.unstablePartition, VG.span, VG.break,++ -- ** Searching+ VG.elem, VG.notElem, VG.find, VG.findIndex, VG.findIndices, VG.elemIndex, VG.elemIndices,++ -- * Folding+ VG.foldl, VG.foldl1, VG.foldl', VG.foldl1', VG.foldr, VG.foldr1, VG.foldr', VG.foldr1',+ VG.ifoldl, VG.ifoldl', VG.ifoldr, VG.ifoldr',++ -- ** Specialised folds+ VG.all, VG.any, VG.and, VG.or,+ VG.sum, VG.product,+ VG.maximum, VG.maximumBy, VG.minimum, VG.minimumBy,+ VG.minIndex, VG.minIndexBy, VG.maxIndex, VG.maxIndexBy,++ -- ** Monadic folds+ VG.foldM, VG.foldM', VG.fold1M, VG.fold1M',+ VG.foldM_, VG.foldM'_, VG.fold1M_, VG.fold1M'_,++ -- ** Monadic sequencing+ VG.sequence, VG.sequence_,++ -- * Prefix sums (scans)+ VG.prescanl, VG.prescanl',+ VG.postscanl, VG.postscanl',+ VG.scanl, VG.scanl', VG.scanl1, VG.scanl1',+ VG.prescanr, VG.prescanr',+ VG.postscanr, VG.postscanr',+ VG.scanr, VG.scanr', VG.scanr1, VG.scanr1',++ -- * Conversions++ -- ** Lists+ VG.toList, VG.fromList, VG.fromListN,++ -- ** Other vector types+ VG.convert,++ -- ** Mutable vectors+ VG.freeze, VG.thaw, VG.copy, VG.unsafeFreeze, VG.unsafeThaw, VG.unsafeCopy+ )+ where++import Data.Monoid hiding (Any)+import qualified Data.Vector as V+import qualified Data.Vector.Mutable as VM+import qualified Data.Vector.Unboxed as VU+import qualified Data.Vector.Generic as VG+import qualified Data.Vector.Generic.Mutable as VGM+import qualified Data.Vector.Unboxed.Mutable as VUM+import Data.Vector.Unboxed.Deriving+import Data.Primitive.Array+import Data.Primitive.ByteArray++import Control.Monad.ST+import Control.Monad.Primitive+import Unsafe.Coerce+import System.IO.Unsafe+import GHC.Prim++import Data.Vector.FunctorLazy.Common+import Data.Vector.FunctorLazy.Mutable++-------------------------------------------------------------------------------+-- data types++data Vector a = Vector+ { vecAny :: !(Array Any)+ , vecInt :: !(ByteArray)+ , len :: !Int+ , control :: !LazyController+ }++instance (Show a) => Show (Vector a) where+ show v = "fromList [" ++ go (VG.length v-1)+ where+ go (-1) = ""+ go i = go (i-1) ++ show (v VG.! i) ++ "," ++instance Functor Vector where+ {-# INLINE fmap #-}+ fmap f v = v { control = LazyController+ { funcL = (unsafeCoerce f):(funcL $ control v)+ , funcC = 1+(funcC $ control v)+ }}++-------------------------------------------------------------------------------+-- vector instances ++type instance VG.Mutable Vector = MVector++instance VG.Vector Vector a where+ {-# INLINE basicUnsafeFreeze #-}+ basicUnsafeFreeze v = do+ frozenAny <- unsafeFreezeArray (mvecAny v)+ frozenInt <- unsafeFreezeByteArray (mvecInt v)+ return $ Vector frozenAny frozenInt (mlen v) (mcontrol v)++ {-# INLINE basicUnsafeThaw #-}+ basicUnsafeThaw v = do+ thawedAny <- unsafeThawArray (vecAny v)+ thawedInt <- unsafeThawByteArray (vecInt v)+ return $ MVector thawedAny thawedInt (len v) (control v)++ {-# INLINE basicLength #-}+ basicLength = len++ {-# INLINE basicUnsafeIndexM #-}+ basicUnsafeIndexM (Vector va vi len (LazyController fl fc)) i = do+ any <- indexArrayM va i+ let count = indexByteArray vi i+ let any' = unsafeCoerce any+ return $ appList any' (take (fc - count) fl)++ {-# INLINE basicUnsafeSlice #-}+ basicUnsafeSlice s len v = error "Data.Vector.FunctorLazy.Vector: slicing not supported"+
+ src/Data/Vector/FunctorLazy/Common.hs view
@@ -0,0 +1,40 @@+{-# LANGUAGE TemplateHaskell #-}+{-# LANGUAGE RankNTypes #-}+{-# LANGUAGE ScopedTypeVariables,TypeFamilies,FlexibleInstances,MultiParamTypeClasses #-}++module Data.Vector.FunctorLazy.Common+ where++import GHC.Prim+import Unsafe.Coerce+import Data.Monoid hiding (Any)++-- | Every position in the super lazy vector is represented by a LazyBox+data LazyBox = LazyBox + { lazyc :: !Int -- ^ how many functions have been applied to this box+ , lazyb :: Any -- ^ current partially evaluated thunk+ }++mkLazyBox :: a -> LazyBox+mkLazyBox a = LazyBox+ { lazyc = 0+ , lazyb = unsafeCoerce a+ }++-- | Records the sequence of fmaps that have occurred +data LazyController = LazyController + { funcL :: [Any]+ , funcC :: {-# UNBOX #-} !Int+ }++instance Monoid LazyController where+ mempty = LazyController [] 0+ mappend a b = LazyController+ { funcL = funcL a ++ funcL b+ , funcC = funcC a + funcC b+ }++appList :: Any -> [Any] -> a+appList box xs = foldr (\f a -> (unsafeCoerce f) a) (unsafeCoerce box) xs++
+ src/Data/Vector/FunctorLazy/Mutable.hs view
@@ -0,0 +1,161 @@+{-# LANGUAGE TemplateHaskell #-}+{-# LANGUAGE RankNTypes #-}+{-# LANGUAGE ScopedTypeVariables,TypeFamilies,FlexibleInstances,MultiParamTypeClasses #-}++-- | Mutable functor-lazy vectors are like mutable boxed vectors, but support mapping a function onto all elements in constant time. All vector operations (except slicing) are fully supported. See <http://github.com/mikeizbicki/functor-lazy> for more details.+module Data.Vector.FunctorLazy.Mutable+ (+ -- * Mutable functorlazy vectors+ MVector(..), IOVector, STVector,++ forceElement, Data.Vector.FunctorLazy.Mutable.mapM,++ -- * Accessors++ -- ** Length information+ VGM.length, VGM.null,++-- -- ** Extracting subvectors+-- slice, init, tail, take, drop, splitAt,+-- unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,++-- -- ** Overlapping+-- overlaps,++ -- * Construction++ -- ** Initialisation+ VGM.new, VGM.unsafeNew, VGM.replicate, VGM.replicateM, VGM.clone,++ -- ** Growing+ VGM.grow, VGM.unsafeGrow,++ -- ** Restricting memory usage+ VGM.clear,++ -- * Accessing individual elements+ VGM.read, VGM.write, VGM.swap,+ VGM.unsafeRead, VGM.unsafeWrite, VGM.unsafeSwap,++ -- * Modifying vectors++ -- ** Filling and copying+ VGM.set, VGM.copy, VGM.move, VGM.unsafeCopy, VGM.unsafeMove+ )+ where++import Data.Monoid hiding (Any)+import qualified Data.Vector as V+import qualified Data.Vector.Mutable as VM+import qualified Data.Vector.Unboxed as VU+import qualified Data.Vector.Generic as VG+import qualified Data.Vector.Generic.Mutable as VGM+import qualified Data.Vector.Unboxed.Mutable as VUM+import Data.Vector.Unboxed.Deriving+import Data.Primitive.Array+import Data.Primitive.ByteArray++import Control.Monad.ST+import Control.Monad.Primitive+import Unsafe.Coerce+import System.IO.Unsafe+import GHC.Prim++import Data.Vector.FunctorLazy.Common++-------------------------------------------------------------------------------+-- data types ++data MVector s a = MVector + { mvecAny :: !(MutableArray s Any)+ , mvecInt :: !(MutableByteArray s)+ , mlen :: !Int+ , mcontrol :: !LazyController+ }++type IOVector = MVector RealWorld+type STVector s = MVector s++uninitialized :: a+uninitialized = error "Data.Vector.FunctorLazy: uninitialized element"++-------------------------------------------------------------------------------+-- vector instances ++instance VGM.MVector MVector a where+ {-# INLINE basicLength #-}+ basicLength (MVector va bi l c) = l++ {-# INLINE basicUnsafeNew #-}+ basicUnsafeNew len = do+ mvecAny <- newArray len uninitialized+ mvecInt <- newByteArray (len*8)+ setByteArray mvecInt 0 len (0::Int)+ return $ MVector+ { mvecAny = mvecAny+ , mvecInt = mvecInt+ , mlen = len+ , mcontrol = mempty+ }++-- {-# INLINE basicUnsafeRead #-}+ basicUnsafeRead (MVector va vi len (LazyController fl fc)) i = do + any <- readArray va i+ count :: Int <- readByteArray vi i+ let val = unsafeCoerce any+ if fc == count+ then return val+ else return $ forceElement (MVector va vi len (LazyController fl fc)) i + +-- {-# INLINE basicUnsafeWrite #-}+ basicUnsafeWrite (MVector va vi len (LazyController fl fc)) i a = do + writeArray va i (unsafeCoerce a)+ writeByteArray vi i fc++ basicOverlaps = error "Data.Vector.FunctorLazy.MVector: basicOverlaps not supported"++-- basicUnsafeSlice s t v = error "Data.Vector.FunctorLazy.Mvector: basicUnsafeSlice" + basicUnsafeSlice s len v = unsafePerformIO $ do+ v' :: MVector RealWorld a <- VGM.basicUnsafeNew len+ do_copy s v'+ return $ unsafeCoerce v' + where+ do_copy i dst + | i < s+len = do+ x <- VGM.basicUnsafeRead (unsafeCoerce v :: MVector RealWorld a) (s+i)+ VGM.basicUnsafeWrite dst i x+ do_copy (i+1) dst+ | otherwise = return ()++ basicUnsafeGrow v by = do+ v' <- VGM.basicUnsafeNew (n+by)+ VGM.basicUnsafeCopy v' v+ return v'+ where+ n = VGM.basicLength v ++-------------------------------------------------------------------------------+-- functions unique to functor lazy vectors++-- | forces all queued functions to be applied at a given index; this does not actually evaluate the functions, however, only stores the appropriate thunk in the index+{-# NOINLINE forceElement #-}+forceElement :: MVector s a -> Int -> a+forceElement (MVector va vi len (LazyController fl fc)) i = unsafePerformIO $ do+ any <- readArray (unsafeCoerce va) i+ count :: Int <- readByteArray (unsafeCoerce vi) i+ let count' = fc + let any' = appList any (take (fc - count) fl) :: a+ writeArray (unsafeCoerce va) i (unsafeCoerce any')+ writeByteArray (unsafeCoerce vi) i (count')+ return any'++-------------------------------------------------------------------------------+-- more efficient functions ++-- | map a function onto all elements in the vector; uses time O(1)+{-# INLINE mapM #-}+mapM :: (Monad m) => (a -> b) -> MVector s a -> m (MVector s b)+mapM f v = return $ v { mcontrol = LazyController+ { funcL = (unsafeCoerce f):(funcL $ mcontrol v)+ , funcC = 1+(funcC $ mcontrol v)+ }}
+ vector-functorlazy.cabal view
@@ -0,0 +1,31 @@+Name: vector-functorlazy+Version: 0.0.1+Synopsis: vectors that perform the fmap operation in constant time+Description: Functor-lazy vectors perform the fmap operation in constant time, whereas other vectors require linear time. All vector operations are supported except for slicing. See <http://github.com/mikeizbicki/vector-funxtorlazy> for details on how this module works under the hood.+Category: Data, Data Structures+License: BSD3+--License-file: LICENSE+Author: Mike izbicki+Maintainer: mike@izbicki.me+Build-Type: Simple+Cabal-Version: >=1.8+homepage: http://github.com/mikeizbicki/vector-functorlazy/+bug-reports: http://github.com/mikeizbicki/vector-functorlazy/issues++Library+ Build-Depends: + base >= 3 && < 5,+ ghc-prim ,+ vector >= 0.9,+ vector-th-unbox >= 0.2,+ primitive >= 0.5++ hs-source-dirs: src+ ghc-options: + -O2 + -fllvm+ -funbox-strict-fields+ Exposed-modules:+ Data.Vector.FunctorLazy+ Data.Vector.FunctorLazy.Mutable+ Data.Vector.FunctorLazy.Common