arraylist (empty) → 0.1.0.0
raw patch · 6 files changed
+580/−0 lines, 6 filesdep +MonadRandomdep +arraylistdep +basesetup-changed
Dependencies added: MonadRandom, arraylist, base, hashable, initialize, primitive, smallcheck, tasty, tasty-smallcheck
Files
- CHANGELOG.md +5/−0
- LICENSE +30/−0
- Setup.hs +2/−0
- arraylist.cabal +59/−0
- src/ArrayList.hs +312/−0
- test/Main.hs +172/−0
+ CHANGELOG.md view
@@ -0,0 +1,5 @@+# Revision history for initialize++## 0.1.0.0 -- 2018-10-25++* First version. Released on an unsuspecting world.
+ LICENSE view
@@ -0,0 +1,30 @@+Copyright (c) 2018, andrewthad++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++ * Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer.++ * Redistributions in binary form must reproduce the above+ copyright notice, this list of conditions and the following+ disclaimer in the documentation and/or other materials provided+ with the distribution.++ * Neither the name of andrewthad nor the names of other+ contributors may be used to endorse or promote products derived+ from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ arraylist.cabal view
@@ -0,0 +1,59 @@+cabal-version: 2.2+name:+ arraylist+version:+ 0.1.0.0+synopsis:+ Memory-efficient ArrayList implementation+description:+ An ArrayList that carries information about the amount of data in it+ that is actually used, and tries to keep space usage to a minimum.+homepage:+ https://github.com/chessai/arraylist+license:+ BSD-3-Clause+license-file:+ LICENSE+author:+ andrewthad+maintainer:+ chessai1996@gmail.com+copyright:+ copyright (c) 2018 andrewthad+category:+ Data+build-type:+ Simple+extra-source-files:+ CHANGELOG.md++library+ exposed-modules:+ ArrayList+ build-depends:+ base >=4.7 && < 4.13+ , primitive >= 0.6.4.0 && < 0.7.0.0+ , initialize >= 0.1.1.0 && < 0.2.0.0+ hs-source-dirs:+ src+ default-language:+ Haskell2010++test-suite test+ type:+ exitcode-stdio-1.0+ hs-source-dirs:+ test+ main-is:+ Main.hs+ build-depends:+ base >= 4.7 && < 4.13+ , arraylist+ , tasty >= 1.1.0.0 && < 1.2.0.0+ , tasty-smallcheck >= 0.8.0.0 && < 0.9.0.0+ , smallcheck >= 1.1.0.0 && < 1.2.0.0+ , primitive >= 0.6.4.0 && < 0.7.0.0+ , hashable >= 1.2.0.0 && < 1.3.0.0+ , MonadRandom >= 0.5.0.0 && < 0.6.0.0+ default-language:+ Haskell2010
+ src/ArrayList.hs view
@@ -0,0 +1,312 @@+-----------------------------------------------------------------------------------++{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE MagicHash #-}+{-# LANGUAGE MultiWayIf #-}+{-# LANGUAGE ScopedTypeVariables #-}++-----------------------------------------------------------------------------------++{-# OPTIONS_GHC -Wall #-}++-----------------------------------------------------------------------------------++module ArrayList+ ( ArrayList+ , size+ , with+ , new+ , free+ , pushR+ , pushArrayR+ , popL+ , dropWhileL+ , dropWhileScanL+ , dropScanL+ , dropL+ , dump+ , dumpMap+ , clear+ , showDebug+ ) where++-----------------------------------------------------------------------------------++import Control.Monad (when)+import Data.Functor ((<$>))+import Control.Applicative ((<*>))+import Data.Bits (Bits(unsafeShiftR))+import Data.Primitive.Addr (Addr(Addr), setAddr)+import Data.Primitive.PrimArray (PrimArray, MutablePrimArray)+import Data.Primitive.Types (Prim())+import Foreign.Storable (Storable(sizeOf, alignment, peek, poke))+import GHC.Exts (RealWorld)+import GHC.Ptr (Ptr(Ptr), castPtr, plusPtr, nullPtr)+import Initialize (Initialize(initialize))+import qualified Data.Primitive as Primitive+import qualified Data.Primitive.PrimArray as PrimArray+import qualified Data.Primitive.Ptr as PrimPtr+import qualified Foreign.Marshal.Alloc as FMAlloc+import qualified Foreign.Marshal.Array as FMArray+import qualified Foreign.Storable as FStorable++-----------------------------------------------------------------------------------++data ArrayList a = ArrayList+ {-# UNPACK #-} !Int -- ^ start index (in elements)+ {-# UNPACK #-} !Int -- ^ used length (in elements)+ {-# UNPACK #-} !Int -- ^ buffer length (in elements)+ {-# UNPACK #-} !(Ptr a) -- ^ all the data++-----------------------------------------------------------------------------------++instance Storable (ArrayList a) where+ sizeOf _ = wordSz * 4;+ alignment _ = wordSz;+ peek ptr = ArrayList+ <$> peek (castPtr ptr)+ <*> peek (plusPtr ptr wordSz)+ <*> peek (plusPtr ptr (wordSz + wordSz))+ <*> peek (plusPtr ptr (wordSz + wordSz + wordSz))+ poke ptr (ArrayList a b c d) = do+ poke (castPtr ptr) a+ poke (plusPtr ptr wordSz) b+ poke (plusPtr ptr (wordSz + wordSz)) c+ poke (plusPtr ptr (wordSz + wordSz + wordSz)) d+ {-# INLINE sizeOf #-}+ {-# INLINE alignment #-}+ {-# INLINE peek #-}+ {-# INLINE poke #-}++instance Storable a => Initialize (ArrayList a) where+ initialize (Ptr addr#) = setAddr (Addr addr#) 4 (0 :: Int)+ {-# INLINE initialize #-}++-----------------------------------------------------------------------------------++{-# INLINE minimizeMemory #-}+minimizeMemory :: forall a. Storable a => ArrayList a -> IO (ArrayList a)+minimizeMemory xs@(ArrayList start len bufLen ptr)+ -- We do not drop below a certain size, since then we would+ -- end up doing frequent reallocations. Although, once the size+ -- reaches zero, we deallocate entirely since this can save a lot+ -- of memory when we have many empty ArrayLists.+ | len == 0 = do+ FMAlloc.free ptr+ return (ArrayList 0 0 0 nullPtr)+ | bufLen <= initialSize = return xs+ | len < eighth bufLen = do+ newPtr <- FMAlloc.mallocBytes (FStorable.sizeOf (undefined :: a) * div bufLen 2)+ FMArray.moveArray newPtr (FMArray.advancePtr ptr start) len+ FMAlloc.free ptr+ return (ArrayList 0 len (div bufLen 2) newPtr)+ | otherwise = return (ArrayList start len bufLen ptr)+ +wordSz :: Int; wordSz = Primitive.sizeOf (undefined :: Int); {-# INLINE wordSz #-}+initialSize :: Int; initialSize = 4; {-# INLINE initialSize #-}++twiceUntilExceeds :: Int -> Int -> Int+twiceUntilExceeds !i !limit = go i where { go !n = if n > limit then n else go (n * 2) }+half, eighth :: Int -> Int;+half x = unsafeShiftR x 1;+eighth x = unsafeShiftR x 3;++-----------------------------------------------------------------------------------++size :: ArrayList a -> Int+{-# INLINE size #-}+size (ArrayList _ len _ _) = len++new :: Storable a => IO (ArrayList a)+new = return (ArrayList 0 0 0 nullPtr)++free :: ArrayList a -> IO ()+free (ArrayList _ _ _ ptr) = FMAlloc.free ptr++with :: Storable a => (ArrayList a -> IO (ArrayList a, b)) -> IO b+with f = do+ initial <- new+ (final, a) <- f initial+ free final+ return a++pushR :: forall a. Storable a => ArrayList a -> a -> IO (ArrayList a)+pushR (ArrayList start len bufLen ptr) a = if start + len < bufLen+ then do+ poke (FMArray.advancePtr ptr (start + len)) a+ return (ArrayList start (len + 1) bufLen ptr)+ else if+ | len == 0 -> do+ when (bufLen /= 0) (fail "ArrayList.pushR: invariant violated")+ when (start /= 0) (fail "ArrayList.pushR: invariant violated")+ when (ptr /= nullPtr) (fail "ArrayList.pushR: invariant violated")+ newPtr <- FMAlloc.mallocBytes (FStorable.sizeOf (undefined :: a) * initialSize)+ poke newPtr a+ return (ArrayList 0 1 initialSize newPtr)+ | len < half bufLen -> do+ FMArray.moveArray ptr (FMArray.advancePtr ptr start) len+ poke (FMArray.advancePtr ptr len) a+ return (ArrayList 0 (len + 1) bufLen ptr)+ | otherwise -> do+ newPtr <- FMAlloc.mallocBytes (FStorable.sizeOf (undefined :: a) * bufLen * 2)+ FMArray.moveArray newPtr (FMArray.advancePtr ptr start) len+ FMAlloc.free ptr+ poke (FMArray.advancePtr newPtr len) a+ return (ArrayList 0 (len + 1) (bufLen * 2) newPtr)++pushArrayR :: forall a. (Storable a, Prim a) => ArrayList a -> PrimArray a -> IO (ArrayList a)+pushArrayR (ArrayList start len bufLen ptr) as = if start + len + asLen <= bufLen+ then do+ PrimArray.copyPrimArrayToPtr (FMArray.advancePtr ptr (start + len)) as 0 asLen+ return (ArrayList start (len + asLen) bufLen ptr)+ else if+ | len == 0 -> do+ when (bufLen /= 0) (fail "ArrayList.pushArrayR: invariant violated")+ when (start /= 0) (fail "ArrayList.pushArrayR: invariant violated")+ when (ptr /= nullPtr) (fail "ArrayList.pushArrayR: invariant violated")+ let newBufLen = twiceUntilExceeds initialSize asLen+ newPtr <- FMAlloc.mallocBytes (FStorable.sizeOf (undefined :: a) * newBufLen)+ PrimArray.copyPrimArrayToPtr newPtr as 0 asLen+ return (ArrayList 0 asLen newBufLen newPtr)+ | len < half bufLen && asLen < half bufLen -> do+ FMArray.moveArray ptr (FMArray.advancePtr ptr start) len+ PrimArray.copyPrimArrayToPtr (FMArray.advancePtr ptr len) as 0 asLen+ return (ArrayList 0 (len + asLen) bufLen ptr)+ | otherwise -> do+ let newBufLen = twiceUntilExceeds (2 * bufLen) (len + asLen)+ newPtr <- FMAlloc.mallocBytes (FStorable.sizeOf (undefined :: a) * newBufLen)+ FMArray.moveArray newPtr (FMArray.advancePtr ptr start) len+ FMAlloc.free ptr+ PrimArray.copyPrimArrayToPtr (FMArray.advancePtr newPtr len) as 0 asLen+ return (ArrayList 0 (len + asLen) newBufLen newPtr)+ where+ asLen = PrimArray.sizeofPrimArray as++popL :: forall a. Storable a => ArrayList a -> IO (ArrayList a, Maybe a)+popL xs@(ArrayList start len bufLen ptr)+ | len < 1 = return (xs, Nothing)+ | otherwise = do+ a <- peek (FMArray.advancePtr ptr start)+ newArrList <- minimizeMemory (ArrayList (start + 1) (len - 1) bufLen ptr)+ return (newArrList, Just a)++{-# INLINE dropWhileL #-}+dropWhileL :: forall a. Storable a+ => ArrayList a+ -> (a -> IO Bool) -- ^ predicate+ -> IO (ArrayList a,Int)+dropWhileL (ArrayList start len bufLen ptr) p = do+ let go :: Int -> IO Int+ go !i = if i < len+ then do+ a <- peek (FMArray.advancePtr ptr (start + i))+ b <- p a+ if b+ then go (i + 1)+ else return i+ else return i+ dropped <- go 0+ newArrList <- minimizeMemory $ ArrayList (start + dropped) (len - dropped) bufLen ptr+ return (newArrList,dropped)+++{-# INLINE dropWhileScanL #-}+dropWhileScanL :: forall a b. Storable a+ => ArrayList a+ -> b+ -> (b -> a -> IO (Bool,b))+ -> IO (ArrayList a,Int,b)+dropWhileScanL (ArrayList start len bufLen ptr) b0 p = do+ let go :: Int -> b -> IO (Int,b)+ go !i !b = if i < len+ then do+ !a <- peek (FMArray.advancePtr ptr (start + i))+ (!shouldContinue,!b') <- p b a+ if shouldContinue+ then go (i + 1) b'+ else return (i,b')+ else return (i,b)+ (dropped,b') <- go 0 b0+ newArrList <- minimizeMemory $ ArrayList (start + dropped) (len - dropped) bufLen ptr+ return (newArrList,dropped,b')++{-# INLINE dropScanL #-}+dropScanL :: forall a b. Storable a+ => ArrayList a+ -> Int+ -> b+ -> (b -> a -> IO b)+ -> IO (ArrayList a, b)+dropScanL (ArrayList start len bufLen ptr) n b0 p = do+ let !m = min n len+ let go :: Int -> b -> IO b+ go !i !b = if i < m+ then do+ a <- peek (FMArray.advancePtr ptr (start + i))+ b' <- p b a+ go (i + 1) b'+ else return b+ b' <- go 0 b0+ newArrList <- minimizeMemory $ ArrayList (start + m) (len - m) bufLen ptr+ return (newArrList,b')++{-# INLINE dropL #-}+dropL :: forall a. Storable a => ArrayList a -> Int -> IO (ArrayList a)+dropL (ArrayList start len bufLen ptr) n = do+ let m = min n len+ minimizeMemory $ ArrayList (start + m) (len - m) bufLen ptr++-- | Deletes all elements from the linked list, copying them+-- into the buffer specified by the pointer. Returns an+-- empty linked list.+dump :: (Prim a, Storable a)+ => ArrayList a -> MutablePrimArray RealWorld a -> Int -> IO (ArrayList a)+dump xs@(ArrayList start len _ ptr) marr ix = do+ PrimPtr.copyPtrToMutablePrimArray marr ix (FMArray.advancePtr ptr start) len+ clear xs++-- | Dump the elements into a 'MutablePrimArray', mapping over them+-- first. This is a fairly niche function.+dumpMap :: (Storable a, Prim b)+ => ArrayList a -> (a -> b) -> MutablePrimArray RealWorld b -> Int -> IO (ArrayList a)+dumpMap xs@(ArrayList start len _ ptr) f marr ix = do+ let go :: Int -> IO ()+ go !i = if i < len+ then do+ a <- FStorable.peekElemOff ptr (start + i)+ PrimArray.writePrimArray marr (ix + i) (f a)+ else return ()+ go 0+ clear xs++clear :: Storable a => ArrayList a -> IO (ArrayList a)+clear xs@(ArrayList _ len _ _) = dropL xs len+{-# INLINE clear #-}++primArrayToListN :: forall a. Prim a => Int -> PrimArray a -> [a]+primArrayToListN len arr = go 0+ where+ go :: Int -> [a]+ go !ix = if ix < len+ then PrimArray.indexPrimArray arr ix : go (ix + 1)+ else []+ +-- | Does not affect the contents of the ArrayList+showDebug :: forall a. (Prim a, Storable a, Show a) => ArrayList a -> IO String+showDebug (ArrayList start len _ ptr) = do+ marr <- PrimArray.newPrimArray len+ PrimPtr.copyPtrToMutablePrimArray marr 0 (plusPtr ptr (start * Primitive.sizeOf (undefined :: a))) len+ arr <- PrimArray.unsafeFreezePrimArray marr+ return (show (primArrayToListN len arr :: [a]))++{-+-- | This should not be used in production code.+dumpList :: (Prim a, Storable a) => ArrayList a -> IO (ArrayList a, [a])+dumpList xs@(ArrayList _ len _ _) = do+ marr <- newPrimArray len+ newXs <- dump xs marr 0+ arr <- unsafeFreezePrimArray marr+ return (newXs,primArrayToListN len arr)+-}++-----------------------------------------------------------------------------------
+ test/Main.hs view
@@ -0,0 +1,172 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE ScopedTypeVariables #-}++{-# OPTIONS_GHC -Wall #-}++module Main (main) where++import Data.Word+import Test.Tasty+import Test.Tasty.SmallCheck+import Test.SmallCheck.Series+import Control.Monad.ST+import qualified ArrayList as AL+import ArrayList (ArrayList)+import Data.Primitive+import Foreign.Storable+import Data.Foldable+import System.IO.Unsafe+import qualified Data.List.NonEmpty as NE+import qualified Data.List as L+import Data.Hashable+import Data.Bifunctor+import Control.Monad.Random.Strict hiding (fromList)++main :: IO ()+main = defaultMain (testGroup "arrayList" arraylistTests)++singletonPrimArray :: forall a. Prim a => a -> PrimArray a+singletonPrimArray x = runST sing where+ sing :: forall s. ST s (PrimArray a)+ sing = do+ arr <- newPrimArray 1+ writePrimArray arr 0 x+ unsafeFreezePrimArray arr++arrayListInsertions :: (Eq a, Show a, Prim a, Storable a) => [a] -> Either String String+arrayListInsertions xs = unsafePerformIO $ AL.with $ \a0 -> do+ a1 <- foldlM AL.pushR a0 xs+ (a2,ys) <- dumpList a1+ return $ (,) a2 $ if xs == ys+ then Right "good"+ else Left ("expected " ++ show xs ++ "but got " ++ show ys)++pushPop :: forall a. (Eq a, Show a, Prim a, Storable a) => [a] -> Either String String+pushPop xs = unsafePerformIO $ AL.with $ \a0 -> do+ a1 <- foldlM AL.pushR a0 xs+ let go :: AL.ArrayList a -> IO (AL.ArrayList a, [a])+ go al = do+ (al',m) <- AL.popL al+ case m of+ Nothing -> return (al',[])+ Just a -> fmap (second (a:)) (go al')+ (a2,ys) <- go a1+ return $ (,) a2 $ if xs == ys+ then Right "good"+ else Left $ "expected " ++ show xs ++ " but got " ++ show ys++arrayListDropWhile :: forall a. (Hashable a, Eq a, Show a, Prim a, Storable a) => [a] -> Either String String+arrayListDropWhile xs = unsafePerformIO $ AL.with $ \a0 ->+ case deterministicShuffle xs of+ [] -> return (a0, Right "good")+ x : _ -> do+ a1 <- foldlM AL.pushR a0 xs+ (a2,_) <- AL.dropWhileL a1 (\y -> return (y /= x))+ (a3,ys) <- dumpList a2+ let expected = L.dropWhile (/= x) xs+ return $ (,) a3 $ if expected == ys+ then Right "good"+ else Left ("expected " ++ show expected ++ " but got " ++ show ys ++ " using pivot of " ++ show x)+ +arrayListInsertArray :: forall a. (Hashable a, Eq a, Show a, Prim a, Storable a)+ => [a] -> Either String String+arrayListInsertArray xs = unsafePerformIO $ AL.with $ \a0 -> do+ a1 <- foldlM AL.pushArrayR a0 (map singletonPrimArray xs)+ let go :: AL.ArrayList a -> IO (AL.ArrayList a, [a])+ go al = do+ (al',m) <- AL.popL al+ case m of+ Nothing -> return (al',[])+ Just a -> fmap (second (a:)) (go al')+ (a2,ys) <- go a1+ return $ (,) a2 $ if xs == ys+ then Right "good"+ else Left $ "expected " ++ show xs ++ " but got " ++ show ys+ +arrayListInsertBigArray :: forall a. (Hashable a, Eq a, Show a, Prim a, Storable a)+ => [a] -> Either String String+arrayListInsertBigArray xs = unsafePerformIO $ AL.with $ \a0 -> do+ a1 <- AL.pushArrayR a0 (fromList xs)+ let go :: AL.ArrayList a -> IO (AL.ArrayList a, [a])+ go al = do+ (al',m) <- AL.popL al+ case m of+ Nothing -> return (al',[])+ Just a -> fmap (second (a:)) (go al')+ (a2,ys) <- go a1+ return $ (,) a2 $ if xs == ys+ then Right "good"+ else Left $ "expected " ++ show xs ++ " but got " ++ show ys++arrayListInsertArrays :: forall a. (Hashable a, Eq a, Show a, Prim a, Storable a)+ => [a] -> Either String String+arrayListInsertArrays xs = unsafePerformIO $ AL.with $ \a0 -> do+ a1 <- AL.pushArrayR a0 (fromList xs)+ a2 <- AL.pushArrayR a1 (fromList xs)+ let go :: AL.ArrayList a -> IO (AL.ArrayList a, [a])+ go al = do+ (al',m) <- AL.popL al+ case m of+ Nothing -> return (al',[])+ Just a -> fmap (second (a:)) (go al')+ (a3,zs) <- go a2+ return $ (,) a3 $ if zs == (xs ++ xs)+ then Right "good"+ else Left $ "expected " ++ show (xs ++ xs) ++ " but got " ++ show zs++-- | This should not be used in production code.+dumpList :: (Prim a, Storable a) => ArrayList a -> IO (ArrayList a, [a])+dumpList xs = do+ let len = AL.size xs+ marr <- newPrimArray len+ newXs <- AL.dump xs marr 0+ arr <- unsafeFreezePrimArray marr+ return (newXs,primArrayToListN len arr)++deterministicShuffle :: Hashable a => [a] -> [a]+deterministicShuffle xs = evalRand (shuffle xs) (mkStdGen (hash xs))++shuffle :: [a] -> Rand StdGen [a]+shuffle [] = return []+shuffle xs = do+ randomPosition <- getRandomR (0, length xs - 1)+ let (left, (a:right)) = L.splitAt randomPosition xs+ fmap (a:) (shuffle (left ++ right))++primArrayToListN :: forall a. Prim a => Int -> PrimArray a -> [a]+primArrayToListN len arr = go 0+ where+ go :: Int -> [a]+ go !ix = if ix < len+ then indexPrimArray arr ix : go (ix + 1)+ else []++arraylistTests :: [TestTree]+arraylistTests =+ [ testPropDepth 10 "arraylist inserts followed by dump (short)" (over word16Series arrayListInsertions)+ , testPropDepth 150 "arraylist inserts followed by dump (long)" (over word32Series arrayListInsertions)+ , testPropDepth 150 "arraylist inserts followed by repeated pop (long)" (over word32Series pushPop)+ , testPropDepth 50 "arraylist dropWhile" (over word32Series arrayListDropWhile)+ , testPropDepth 50 "insert array" (over word32Series arrayListInsertArray)+ , testPropDepth 100 "insert big array" (over word32Series arrayListInsertBigArray)+ , testPropDepth 100 "insert big arrays" (over word32Series arrayListInsertArrays)+-- , testPropDepth 150 "arraylist push, pop, twice (long)" (over word32Series pushPopTwice)+ ]++testPropDepth :: Testable IO a => Int -> String -> a -> TestTree+testPropDepth n name = localOption (SmallCheckDepth n) . testProperty name++scanSeries :: forall m a. (a -> [a]) -> a -> Series m [a]+scanSeries f x0 = generate $ \n ->+ map toList $ concat $ take n $ iterate+ (\ys -> ys >>= \xs@(x NE.:| _) -> f x >>= \z -> [z NE.:| (toList xs)])+ [x0 NE.:| []]++word16Series :: Series m [Word16]+word16Series = (scanSeries (\n -> [n + 89, n + 71]) 0)++word32Series :: Series m [Word32]+word32Series = (scanSeries (\n -> [n + 73]) 0)+