{- | Functions for 'StorableVector' that allow control of the size of individual chunks. This is import for an application like the following: You want to mix audio signals that are relatively shifted. The structure of chunks of three streams may be illustrated as: > [____] [____] [____] [____] ... > [____] [____] [____] [____] ... > [____] [____] [____] [____] ... When we mix the streams (@zipWith3 (\x y z -> x+y+z)@) with respect to the chunk structure of the first signal, computing the first chunk requires full evaluation of all leading chunks of the stream. However the last value of the third leading chunk is much later in time than the last value of the first leading chunk. We like to reduce these dependencies using a different chunk structure, say > [____] [____] [____] [____] ... > [__] [____] [____] [____] ... > [] [____] [____] [____] ... -} module Data.StorableVector.Lazy.Pattern ( Vector, ChunkSize, chunkSize, defaultChunkSize, LazySize, empty, singleton, pack, unpack, packWith, unpackWith, unfoldrN, iterateN, cycle, replicate, null, length, cons, append, concat, map, reverse, foldl, foldl', any, all, maximum, minimum, viewL, viewR, switchL, switchR, scanl, mapAccumL, mapAccumR, crochetL, take, drop, splitAt, takeVectorPattern, splitAtVectorPattern, dropMarginRem, dropMargin, dropWhile, takeWhile, span, filter, zipWith, zipWith3, zipWith4, zipWithSize, zipWithSize3, zipWithSize4, {- pad, cancelNullVector, -} ) where import Numeric.NonNegative.Class ((-|)) import qualified Numeric.NonNegative.Chunky as LS import qualified Data.StorableVector.Lazy as LSV import qualified Data.StorableVector as V import Data.StorableVector.Lazy (Vector(SV), ChunkSize(ChunkSize)) import Data.StorableVector.Lazy ( chunkSize, defaultChunkSize, empty, singleton, unpack, unpackWith, cycle, null, cons, append, concat, map, reverse, foldl, foldl', any, all, maximum, minimum, viewL, viewR, switchL, switchR, scanl, mapAccumL, mapAccumR, crochetL, dropMarginRem, dropMargin, dropWhile, takeWhile, span, filter, zipWith, zipWith3, zipWith4, ) import qualified Data.List as List import qualified Data.List.HT as ListHT import Data.Tuple.HT (mapPair, mapFst, forcePair, swap, ) import Control.Monad (liftM2, liftM3, liftM4, guard, ) import Foreign.Storable (Storable) import Prelude hiding (length, (++), iterate, foldl, map, repeat, replicate, null, zip, zipWith, zipWith3, drop, take, splitAt, takeWhile, dropWhile, reverse, any, all, concat, cycle, filter, maximum, minimum, scanl, span, ) {- import Data.Maybe (Maybe(Just, Nothing), ) import Prelude (Int, (.), ($), fst, snd, (<=), flip, curry, return, fmap, not, uncurry, ) -} type LazySize = LS.T ChunkSize -- * Introducing and eliminating 'Vector's {- Actually, this is lazy enough: > LSV.unpack $ pack (LS.fromChunks [10,15]) (['a'..'y'] List.++ Prelude.undefined) "abcdefghijklmnopqrstuvwxy" -} pack :: (Storable a) => LazySize -> [a] -> Vector a pack size = fst . unfoldrN size ListHT.viewL {-# INLINE packWith #-} packWith :: (Storable b) => LazySize -> (a -> b) -> [a] -> Vector b packWith size f = fst . unfoldrN size (fmap (mapFst f) . ListHT.viewL) {- {-# INLINE unfoldrNAlt #-} unfoldrNAlt :: (Storable b) => LazySize -> (a -> Maybe (b,a)) -> a -> (Vector b, Maybe a) unfoldrNAlt (LS.Cons size) f x = let go sz y = case sz of [] -> ([], y) (ChunkSize s : ss) -> maybe ([], Nothing) ((\(c,a1) -> mapFst (c:) $ go ss a1) . V.unfoldrN s (fmap (mapSnd f))) (f y) in mapFst SV $ go size (Just x) -} {-# INLINE unfoldrN #-} unfoldrN :: (Storable b) => LazySize -> (a -> Maybe (b,a)) -> a -> (Vector b, Maybe a) unfoldrN size f = let go sz y = forcePair $ case sz of [] -> ([], y) (ChunkSize s : ss) -> let m = do a0 <- y let p = V.unfoldrN s f a0 guard (not (V.null (fst p))) return p in case m of Nothing -> ([], Nothing) Just (c,a1) -> mapFst (c:) $ go ss a1 in mapFst SV . go (LS.toChunks size) . Just {-# INLINE iterateN #-} iterateN :: Storable a => LazySize -> (a -> a) -> a -> Vector a iterateN size f = fst . unfoldrN size (\x -> Just (x, f x)) {- Tries to be time and memory efficient by reusing subvectors of a chunk until a larger chunk is needed. However, it can be a memory leak if a huge chunk is followed by many little ones. -} replicate :: Storable a => LazySize -> a -> Vector a replicate size x = SV $ snd $ List.mapAccumL (\v (ChunkSize m) -> if m <= V.length v then (v, V.take m v) else let v1 = V.replicate m x in (v1,v1)) V.empty $ LS.toChunks size {- replicate :: Storable a => LazySize -> a -> Vector a replicate size x = SV $ List.map (\(ChunkSize m) -> V.replicate m x) (LS.toChunks size) -} -- * Basic interface length :: Vector a -> LazySize length = LS.fromChunks . List.map chunkLength . LSV.chunks chunkLength :: V.Vector a -> ChunkSize chunkLength = ChunkSize . V.length decrementLimit :: V.Vector a -> LazySize -> LazySize decrementLimit x y = y -| LS.fromNumber (chunkLength x) intFromChunkSize :: ChunkSize -> Int intFromChunkSize (ChunkSize x) = x intFromLazySize :: LazySize -> Int intFromLazySize = List.sum . List.map intFromChunkSize . LS.toChunks -- * sub-vectors {- | Generates laziness breaks wherever either the lazy length number or the vector has a chunk boundary. -} {-# INLINE take #-} take :: (Storable a) => LazySize -> Vector a -> Vector a take n = fst . splitAt n {- | Preserves the chunk pattern of the lazy vector. -} {-# INLINE takeVectorPattern #-} takeVectorPattern :: (Storable a) => LazySize -> Vector a -> Vector a takeVectorPattern _ (SV []) = empty takeVectorPattern n (SV (x:xs)) = if List.null (LS.toChunks n) then empty else let remain = decrementLimit x n in SV $ uncurry (:) $ if LS.isNull remain then (V.take (intFromLazySize n) x, []) else (x, LSV.chunks $ take remain $ LSV.fromChunks xs) {-# INLINE drop #-} drop :: (Storable a) => LazySize -> Vector a -> Vector a drop size xs = List.foldl (flip (LSV.drop . intFromChunkSize)) xs (LS.toChunks size) {-# INLINE splitAt #-} splitAt :: (Storable a) => LazySize -> Vector a -> (Vector a, Vector a) splitAt size xs = mapFst LSV.concat $ swap $ List.mapAccumL (\xs0 n -> swap $ LSV.splitAt (intFromChunkSize n) xs0) xs (LS.toChunks size) {-# INLINE splitAtVectorPattern #-} splitAtVectorPattern :: (Storable a) => LazySize -> Vector a -> (Vector a, Vector a) splitAtVectorPattern n0 = forcePair . if List.null (LS.toChunks n0) then (,) empty else let recourse n xt = forcePair $ case xt of [] -> ([], []) (x:xs) -> let remain = decrementLimit x n in if LS.isNull remain then mapPair ((:[]), (:xs)) $ V.splitAt (intFromLazySize n) x else mapFst (x:) $ recourse remain xs in mapPair (SV, SV) . recourse n0 . LSV.chunks {-# INLINE [0] zipWithSize #-} zipWithSize :: (Storable a, Storable b, Storable c) => LazySize -> (a -> b -> c) -> Vector a -> Vector b -> Vector c zipWithSize size f = curry (fst . unfoldrN size (\(xt,yt) -> liftM2 (\(x,xs) (y,ys) -> (f x y, (xs,ys))) (viewL xt) (viewL yt))) {-# INLINE zipWithSize3 #-} zipWithSize3 :: (Storable a, Storable b, Storable c, Storable d) => LazySize -> (a -> b -> c -> d) -> (Vector a -> Vector b -> Vector c -> Vector d) zipWithSize3 size f s0 s1 s2 = fst $ unfoldrN size (\(xt,yt,zt) -> liftM3 (\(x,xs) (y,ys) (z,zs) -> (f x y z, (xs,ys,zs))) (viewL xt) (viewL yt) (viewL zt)) (s0,s1,s2) {-# INLINE zipWithSize4 #-} zipWithSize4 :: (Storable a, Storable b, Storable c, Storable d, Storable e) => LazySize -> (a -> b -> c -> d -> e) -> (Vector a -> Vector b -> Vector c -> Vector d -> Vector e) zipWithSize4 size f s0 s1 s2 s3 = fst $ unfoldrN size (\(xt,yt,zt,wt) -> liftM4 (\(x,xs) (y,ys) (z,zs) (w,ws) -> (f x y z w, (xs,ys,zs,ws))) (viewL xt) (viewL yt) (viewL zt) (viewL wt)) (s0,s1,s2,s3) {- {- | Ensure a minimal length of the list by appending pad values. -} {-# ONLINE pad #-} pad :: (Storable a) => ChunkSize -> a -> Int -> Vector a -> Vector a pad size y n0 = let recourse n xt = if n<=0 then xt else case xt of [] -> chunks $ replicate size n y x:xs -> x : recourse (n - V.length x) xs in SV . recourse n0 . chunks padAlt :: (Storable a) => ChunkSize -> a -> Int -> Vector a -> Vector a padAlt size x n xs = append xs (let m = length xs in if n>m then replicate size (n-m) x else empty) -}