packages feed

mutable-containers 0.3.3 → 0.3.4

raw patch · 21 files changed

+1033/−999 lines, 21 filesdep +gaugedep −criteriondep ~base

Dependencies added: gauge

Dependencies removed: criterion

Dependency ranges changed: base

Files

ChangeLog.md view
@@ -1,3 +1,7 @@+## 0.3.4++* Switch to gauge+ ## 0.3.3  * Move into mono-traversable repo
− Data/Mutable.hs 
@@ -1,68 +0,0 @@--- | Classes and concrete implementations for mutable data structures.------ For more information on the design of this library, see the README file,--- also available at <http://www.stackage.org/package/mutable-containers>.-module Data.Mutable-    ( -- * Data types-      -- ** Single-cell mutable references-      PRef-    , IOPRef-    , asPRef-    , URef-    , IOURef-    , asURef-    , SRef-    , IOSRef-    , asSRef-    , BRef-    , IOBRef-    , asBRef-      -- *** Standard re-exports-    , IORef-    , asIORef-    , STRef-    , asSTRef-    , MutVar-    , asMutVar-      -- ** Collections/queues-    , Deque-    , UDeque-    , asUDeque-    , SDeque-    , asSDeque-    , BDeque-    , asBDeque-    , DLList-    , asDLList-      -- * Type classes-    , MutableContainer (..)-    , MutableRef (..)-    , MutableAtomicRef (..)-    , MutableCollection (..)-    , MutablePushFront (..)-    , MutablePushBack (..)-    , MutablePopFront (..)-    , MutablePopBack (..)-      -- * Constraint kinds-    , MutableQueue-    , MutableStack-    , MutableDeque-      -- * Convenience re-exports-    , PrimMonad-    , PrimState-    , RealWorld-    , Prim-    , Unbox-    , Storable-    ) where--import Data.Mutable.Class-import Data.Mutable.URef-import Data.Mutable.SRef-import Data.Mutable.PRef-import Data.Mutable.BRef-import Data.Mutable.Deque-import Data.Mutable.DLList-import Data.Vector.Unboxed (Unbox)-import Data.Primitive (Prim)-import Data.Vector.Storable (Storable)
− Data/Mutable/BRef.hs 
@@ -1,71 +0,0 @@-{-# LANGUAGE TypeFamilies #-}--- | Use 1-length mutable boxed vectors for mutable references.------ Motivated by: <http://stackoverflow.com/questions/27261813/why-is-my-little-stref-int-require-allocating-gigabytes> and ArrayRef.-module Data.Mutable.BRef-    ( -- * Types-      BRef-    , IOBRef-      -- * Functions-    , asBRef-    , MutableRef (..)-    ) where--import           Control.Monad               (liftM)-import           Data.Monoid                 (Monoid, mempty)-import           Data.MonoTraversable        (Element)-import           Data.Mutable.Class-import           Data.Sequences              (IsSequence)-import qualified Data.Vector.Generic.Mutable as V-import qualified Data.Vector.Mutable         as VB---- | A boxed vector reference, supporting any monad.------ Since 0.2.0-newtype BRef s a = BRef (VB.MVector s a)---- |--- Since 0.2.0-asBRef :: BRef s a -> BRef s a-asBRef x = x-{-# INLINE asBRef #-}---- | A boxed IO vector reference.-type IOBRef = BRef (PrimState IO)--instance MutableContainer (BRef s a) where-    type MCState (BRef s a) = s-instance MutableRef (BRef s a) where-    type RefElement (BRef s a) = a--    newRef = liftM BRef . V.replicate 1-    {-# INLINE newRef#-}--    readRef (BRef v) = V.unsafeRead v 0-    {-# INLINE readRef #-}--    writeRef (BRef v) = V.unsafeWrite v 0-    {-# INLINE writeRef #-}--    modifyRef (BRef v) f = V.unsafeRead v 0 >>= V.unsafeWrite v 0 . f-    {-# INLINE modifyRef #-}--    modifyRef' = modifyRef-    {-# INLINE modifyRef' #-}--instance Monoid w => MutableCollection (BRef s w) where-    type CollElement (BRef s w) = Element w-    newColl = newRef mempty-    {-# INLINE newColl #-}-instance IsSequence seq => MutablePushFront (BRef s seq) where-    pushFront = pushFrontRef-    {-# INLINE pushFront #-}-instance IsSequence seq => MutablePushBack (BRef s seq) where-    pushBack = pushBackRef-    {-# INLINE pushBack #-}-instance IsSequence seq => MutablePopFront (BRef s seq) where-    popFront = popFrontRef-    {-# INLINE popFront #-}-instance IsSequence seq => MutablePopBack (BRef s seq) where-    popBack = popBackRef-    {-# INLINE popBack #-}
− Data/Mutable/Class.hs 
@@ -1,373 +0,0 @@-{-# LANGUAGE ConstraintKinds   #-}-{-# LANGUAGE FlexibleContexts  #-}-{-# LANGUAGE FlexibleInstances #-}-{-# LANGUAGE TypeFamilies      #-}--- | Various typeclasses for mutable containers.-module Data.Mutable.Class-    ( PrimMonad-    , PrimState-    , RealWorld-    , MutableQueue-    , MutableStack-    , MutableDeque-    , IORef-    , asIORef-    , STRef-    , asSTRef-    , MutVar-    , asMutVar-    , MutableContainer (..)-    , MutableRef (..)-    , MutableAtomicRef (..)-    , MutableCollection (..)-    , MutablePushFront (..)-    , MutablePushBack (..)-    , MutablePopFront (..)-    , MutablePopBack (..)-    , pushFrontRef-    , pushBackRef-    , popFrontRef-    , popBackRef-    ) where--import           Control.Monad.Primitive-import           Data.IORef-import           Data.Monoid-import           Data.MonoTraversable    (Element)-import           Data.Primitive.MutVar-import qualified Data.Sequences          as Seqs-import           Data.STRef---- | The parent typeclass for all mutable containers.------ Since 0.2.0-class MutableContainer c where-    -- | Associated type giving the primitive state token for the given-    -- container, much like 'PrimState' from primitive.-    ---    -- Since 0.2.0-    type MCState c--instance MutableContainer (IORef a) where-    type MCState (IORef a) = PrimState IO-instance MutableContainer (STRef s a) where-    type MCState (STRef s a) = s-instance MutableContainer (MutVar s a) where-    type MCState (MutVar s a) = s---- | Typeclass for single-cell mutable references.------ Since 0.2.0-class MutableContainer c => MutableRef c where-    -- | Associated type giving the type of the value inside the mutable-    -- reference.-    ---    -- Since 0.2.0-    type RefElement c--    -- | Create a new mutable reference with the given value.-    ---    -- Since 0.2.0-    newRef :: (PrimMonad m, PrimState m ~ MCState c)-           => RefElement c-           -> m c--    -- | Read the current value in the mutable reference.-    ---    -- Since 0.2.0-    readRef :: (PrimMonad m, PrimState m ~ MCState c)-            => c-            -> m (RefElement c)--    -- | Write a new value to the mutable reference.-    ---    -- Since 0.2.0-    writeRef :: (PrimMonad m, PrimState m ~ MCState c)-             => c-             -> RefElement c-             -> m ()--    -- | Modify the value in the mutable reference, without necessarily forcing the result.-    ---    -- Note: some implementations /will/ force the result, in particular-    -- @PRef@, @SRef@, and @URef@.-    ---    -- Since 0.2.0-    modifyRef :: (PrimMonad m, PrimState m ~ MCState c)-              => c-              -> (RefElement c -> RefElement c)-              -> m ()--    -- | Modify the value in the mutable reference, forcing the result.-    ---    -- Since 0.2.0-    modifyRef' :: (PrimMonad m, PrimState m ~ MCState c)-               => c-               -> (RefElement c -> RefElement c)-               -> m ()--instance MutableRef (IORef a) where-    type RefElement (IORef a) = a-    newRef = primToPrim . newIORef-    {-# INLINE newRef #-}-    readRef = primToPrim . readIORef-    {-# INLINE readRef #-}-    writeRef c = primToPrim . writeIORef c-    {-# INLINE writeRef #-}-    modifyRef c = primToPrim . modifyIORef c-    {-# INLINE modifyRef #-}-    modifyRef' c = primToPrim . modifyIORef' c-    {-# INLINE modifyRef' #-}-instance MutableRef (STRef s a) where-    type RefElement (STRef s a) = a-    newRef = primToPrim . newSTRef-    {-# INLINE newRef #-}-    readRef = primToPrim . readSTRef-    {-# INLINE readRef #-}-    writeRef c = primToPrim . writeSTRef c-    {-# INLINE writeRef #-}-    modifyRef c = primToPrim . modifySTRef c-    {-# INLINE modifyRef #-}-    modifyRef' c = primToPrim . modifySTRef' c-    {-# INLINE modifyRef' #-}-instance MutableRef (MutVar s a) where-    type RefElement (MutVar s a) = a-    newRef = newMutVar-    {-# INLINE newRef #-}-    readRef = readMutVar-    {-# INLINE readRef #-}-    writeRef = writeMutVar-    {-# INLINE writeRef #-}-    modifyRef = modifyMutVar-    {-# INLINE modifyRef #-}-    modifyRef' = modifyMutVar'-    {-# INLINE modifyRef' #-}---- | @MutableRef@s that provide for atomic modifications of their contents.------ Since 0.2.0-class MutableRef c => MutableAtomicRef c where-    -- | Modify the value without necessarily forcing the result.-    ---    -- Since 0.2.0-    atomicModifyRef-        :: (PrimMonad m, PrimState m ~ MCState c)-        => c-        -> (RefElement c -> (RefElement c, a))-        -> m a--    -- | Modify the value, forcing the result.-    ---    -- Since 0.2.0-    atomicModifyRef'-        :: (PrimMonad m, PrimState m ~ MCState c)-        => c-        -> (RefElement c -> (RefElement c, a))-        -> m a-instance MutableAtomicRef (IORef a) where-    atomicModifyRef c = primToPrim . atomicModifyIORef c-    {-# INLINE atomicModifyRef #-}-    atomicModifyRef' c = primToPrim . atomicModifyIORef' c-    {-# INLINE atomicModifyRef' #-}-instance MutableAtomicRef (MutVar s a) where-    atomicModifyRef = atomicModifyMutVar-    {-# INLINE atomicModifyRef #-}-    atomicModifyRef' = atomicModifyMutVar'-    {-# INLINE atomicModifyRef' #-}---- | Containers which contain 0 or more values.------ Since 0.2.0-class MutableContainer c => MutableCollection c where-    -- | The type of each value in the collection.-    ---    -- Since 0.2.0-    type CollElement c--    -- | Create a new, empty collection.-    ---    -- Since 0.2.0-    newColl :: (PrimMonad m, PrimState m ~ MCState c)-            => m c-instance Monoid w => MutableCollection (IORef w) where-    type CollElement (IORef w) = Element w-    newColl = newRef mempty-    {-# INLINE newColl #-}-instance Monoid w => MutableCollection (STRef s w) where-    type CollElement (STRef s w) = Element w-    newColl = newRef mempty-    {-# INLINE newColl #-}-instance Monoid w => MutableCollection (MutVar s w) where-    type CollElement (MutVar s w) = Element w-    newColl = newRef mempty-    {-# INLINE newColl #-}---- | Take a value from the front of the collection, if available.------ Since 0.2.0-class MutableCollection c => MutablePopFront c where-    -- | Take a value from the front of the collection, if available.-    ---    -- Since 0.2.0-    popFront :: (PrimMonad m, PrimState m ~ MCState c)-             => c-             -> m (Maybe (CollElement c))-popFrontRef-    :: ( PrimMonad m-       , PrimState m ~ MCState c-       , MutableRef c-       , CollElement c ~ Element (RefElement c)-       , Seqs.IsSequence (RefElement c)-       )-    => c-    -> m (Maybe (CollElement c))-popFrontRef c = do-    l <- readRef c-    case Seqs.uncons l of-        Nothing -> return Nothing-        Just (x, xs) -> do-            writeRef c xs-            return (Just x)-{-# INLINE popFrontRef #-}-instance Seqs.IsSequence a => MutablePopFront (IORef a) where-    popFront = popFrontRef-    {-# INLINE popFront #-}-instance Seqs.IsSequence a => MutablePopFront (STRef s a) where-    popFront = popFrontRef-    {-# INLINE popFront #-}-instance Seqs.IsSequence a => MutablePopFront (MutVar s a) where-    popFront = popFrontRef-    {-# INLINE popFront #-}---- | Place a value at the front of the collection.------ Since 0.2.0-class MutableCollection c => MutablePushFront c where-    -- | Place a value at the front of the collection.-    ---    -- Since 0.2.0-    pushFront :: (PrimMonad m, PrimState m ~ MCState c)-              => c-              -> CollElement c-              -> m ()-pushFrontRef-    :: ( PrimMonad m-       , PrimState m ~ MCState c-       , MutableRef c-       , CollElement c ~ Element (RefElement c)-       , Seqs.IsSequence (RefElement c)-       )-    => c-    -> CollElement c-    -> m ()-pushFrontRef c e = modifyRef' c (Seqs.cons e)-{-# INLINE pushFrontRef #-}-instance Seqs.IsSequence a => MutablePushFront (IORef a) where-    pushFront = pushFrontRef-    {-# INLINE pushFront #-}-instance Seqs.IsSequence a => MutablePushFront (STRef s a) where-    pushFront = pushFrontRef-    {-# INLINE pushFront #-}-instance Seqs.IsSequence a => MutablePushFront (MutVar s a) where-    pushFront = pushFrontRef-    {-# INLINE pushFront #-}---- | Take a value from the back of the collection, if available.------ Since 0.2.0-class MutableCollection c => MutablePopBack c where-    -- | Take a value from the back of the collection, if available.-    ---    -- Since 0.2.0-    popBack :: (PrimMonad m, PrimState m ~ MCState c)-            => c-            -> m (Maybe (CollElement c))-popBackRef-    :: ( PrimMonad m-       , PrimState m ~ MCState c-       , MutableRef c-       , CollElement c ~ Element (RefElement c)-       , Seqs.IsSequence (RefElement c)-       )-    => c-    -> m (Maybe (CollElement c))-popBackRef c = do-    l <- readRef c-    case Seqs.unsnoc l of-        Nothing -> return Nothing-        Just (xs, x) -> do-            writeRef c xs-            return (Just x)-{-# INLINE popBackRef #-}-instance Seqs.IsSequence a => MutablePopBack (IORef a) where-    popBack = popBackRef-    {-# INLINE popBack #-}-instance Seqs.IsSequence a => MutablePopBack (STRef s a) where-    popBack = popBackRef-    {-# INLINE popBack #-}-instance Seqs.IsSequence a => MutablePopBack (MutVar s a) where-    popBack = popBackRef-    {-# INLINE popBack #-}---- | Place a value at the back of the collection.------ Since 0.2.0-class MutableCollection c => MutablePushBack c where-    -- | Place a value at the back of the collection.-    ---    -- Since 0.2.0-    pushBack :: (PrimMonad m, PrimState m ~ MCState c)-             => c-             -> CollElement c-             -> m ()-pushBackRef-    :: ( PrimMonad m-       , PrimState m ~ MCState c-       , MutableRef c-       , CollElement c ~ Element (RefElement c)-       , Seqs.IsSequence (RefElement c)-       )-    => c-    -> CollElement c-    -> m ()-pushBackRef c e = modifyRef' c (`Seqs.snoc` e)-{-# INLINE pushBackRef #-}-instance Seqs.IsSequence a => MutablePushBack (IORef a) where-    pushBack = pushBackRef-    {-# INLINE pushBack #-}-instance Seqs.IsSequence a => MutablePushBack (STRef s a) where-    pushBack = pushBackRef-    {-# INLINE pushBack #-}-instance Seqs.IsSequence a => MutablePushBack (MutVar s a) where-    pushBack = pushBackRef-    {-# INLINE pushBack #-}---- | Collections which allow pushing and popping at the front (aka FIFOs).------ Since 0.2.0-type MutableQueue c = (MutablePopFront c, MutablePushBack c)---- | Collections which allow pushing at the back and popping at the front (aka FILOs).------ Since 0.2.0-type MutableStack c = (MutablePopFront c, MutablePushFront c)---- | Collections which allow pushing and popping at the front and back.------ Since 0.2.0-type MutableDeque c = (MutableQueue c, MutablePushFront c, MutablePopBack c)---- |--- Since 0.2.0-asIORef :: IORef a -> IORef a-asIORef = id---- |--- Since 0.2.0-asSTRef :: STRef s a -> STRef s a-asSTRef = id---- |--- Since 0.2.0-asMutVar :: MutVar s a -> MutVar s a-asMutVar = id
− Data/Mutable/DLList.hs 
@@ -1,101 +0,0 @@-{-# LANGUAGE TypeFamilies #-}--- | Doubly-linked list-module Data.Mutable.DLList-    ( DLList-    , asDLList-    , module Data.Mutable.Class-    ) where--import Data.Mutable.Class--data Node s a = Node-    a-    (MutVar s (Maybe (Node s a))) -- previous-    (MutVar s (Maybe (Node s a))) -- next---- | A doubly-linked list.------ Since 0.3.0-data DLList s a = DLList (MutVar s (Maybe (Node s a))) (MutVar s (Maybe (Node s a)))---- |--- Since 0.2.0-asDLList :: DLList s a -> DLList s a-asDLList = id-{-# INLINE asDLList #-}--instance MutableContainer (DLList s a) where-    type MCState (DLList s a) = s-instance MutableCollection (DLList s a) where-    type CollElement (DLList s a) = a-    newColl = do-        x <- newRef $! Nothing-        y <- newRef $! Nothing-        return $! DLList x y-    {-# INLINE newColl #-}-instance MutablePopFront (DLList s a) where-    popFront (DLList frontRef backRef) = do-        mfront <- readRef frontRef-        case mfront of-            Nothing -> return Nothing-            Just (Node val _ nextRef) -> do-                mnext <- readRef nextRef-                case mnext of-                    Nothing -> do-                        writeRef frontRef $! Nothing-                        writeRef backRef $! Nothing-                    Just next@(Node _ prevRef _) -> do-                        writeRef prevRef $! Nothing-                        writeRef frontRef $! Just next-                return $ Just val-    {-# INLINE popFront #-}-instance MutablePopBack (DLList s a) where-    popBack (DLList frontRef backRef) = do-        mback <- readRef backRef-        case mback of-            Nothing -> return Nothing-            Just (Node val prevRef _) -> do-                mprev <- readRef prevRef-                case mprev of-                    Nothing -> do-                        writeRef frontRef $! Nothing-                        writeRef backRef $! Nothing-                    Just prev@(Node _ _ nextRef) -> do-                        writeRef nextRef $! Nothing-                        writeRef backRef (Just prev)-                return $ Just val-    {-# INLINE popBack #-}-instance MutablePushFront (DLList s a) where-    pushFront (DLList frontRef backRef) val = do-        mfront <- readRef frontRef-        case mfront of-            Nothing -> do-                prevRef <- newRef $! Nothing-                nextRef <- newRef $! Nothing-                let node = Just $ Node val prevRef nextRef-                writeRef frontRef node-                writeRef backRef node-            Just front@(Node _ prevRef _) -> do-                prevRefNew <- newRef $! Nothing-                nextRef <- newRef $ Just front-                let node = Just $ Node val prevRefNew nextRef-                writeRef prevRef node-                writeRef frontRef node-    {-# INLINE pushFront #-}-instance MutablePushBack (DLList s a) where-    pushBack (DLList frontRef backRef) val = do-        mback <- readRef backRef-        case mback of-            Nothing -> do-                prevRef <- newRef $! Nothing-                nextRef <- newRef $! Nothing-                let node = Just $! Node val prevRef nextRef-                writeRef frontRef $! node-                writeRef backRef $! node-            Just back@(Node _ _ nextRef) -> do-                nextRefNew <- newRef $! Nothing-                prevRef <- newRef $! Just back-                let node = Just $! Node val prevRef nextRefNew-                writeRef nextRef $! node-                writeRef backRef $! node-    {-# INLINE pushBack #-}
− Data/Mutable/Deque.hs 
@@ -1,152 +0,0 @@-{-# LANGUAGE TypeFamilies #-}-module Data.Mutable.Deque-    ( Deque-    , UDeque-    , asUDeque-    , SDeque-    , asSDeque-    , BDeque-    , asBDeque-    , module Data.Mutable.Class-    ) where--import           Control.Exception            (assert)-import           Control.Monad                (liftM)-import           Data.Mutable.Class-import qualified Data.Vector.Generic.Mutable  as V-import qualified Data.Vector.Mutable          as B-import qualified Data.Vector.Storable.Mutable as S-import qualified Data.Vector.Unboxed.Mutable  as U--data DequeState v s a = DequeState-    (v s a)-    {-# UNPACK #-} !Int -- start-    {-# UNPACK #-} !Int -- size---- | A double-ended queue supporting any underlying vector type and any monad.------ This implements a circular double-ended queue with exponential growth.------ Since 0.2.0-newtype Deque v s a = Deque (MutVar s (DequeState v s a))---- | A 'Deque' specialized to unboxed vectors.------ Since 0.2.0-type UDeque = Deque U.MVector---- | A 'Deque' specialized to storable vectors.------ Since 0.2.0-type SDeque = Deque S.MVector---- | A 'Deque' specialized to boxed vectors.------ Since 0.2.0-type BDeque = Deque B.MVector---- |--- Since 0.2.0-asUDeque :: UDeque s a -> UDeque s a-asUDeque = id---- |--- Since 0.2.0-asSDeque :: SDeque s a -> SDeque s a-asSDeque = id---- |--- Since 0.2.0-asBDeque :: BDeque s a -> BDeque s a-asBDeque = id--instance MutableContainer (Deque v s a) where-    type MCState (Deque v s a) = s-instance V.MVector v a => MutableCollection (Deque v s a) where-    type CollElement (Deque v s a) = a-    newColl = do-        v <- V.new baseSize-        liftM Deque $ newRef (DequeState v 0 0)-      where-        baseSize = 32-    {-# INLINE newColl #-}-instance V.MVector v a => MutablePopFront (Deque v s a) where-    popFront (Deque var) = do-        DequeState v start size <- readRef var-        if size == 0-            then return Nothing-            else do-                x <- V.unsafeRead v start-                let start' = start + 1-                    start''-                        | start' >= V.length v = 0-                        | otherwise = start'-                writeRef var $! DequeState v start'' (size - 1)-                return $! Just x-    {-# INLINE popFront #-}-instance V.MVector v a => MutablePopBack (Deque v s a) where-    popBack (Deque var) = do-        DequeState v start size <- readRef var-        if size == 0-            then return Nothing-            else do-                let size' = size - 1-                    end = start + size'-                    end'-                        | end >= V.length v = end - V.length v-                        | otherwise = end-                x <- V.unsafeRead v end'-                writeRef var $! DequeState v start size'-                return $! Just x-    {-# INLINE popBack #-}-instance V.MVector v a => MutablePushFront (Deque v s a) where-    pushFront (Deque var) x = do-        DequeState v start size <- readRef var-        inner v start size-      where-        inner v start size = do-            if size >= V.length v-                then newVector v start size inner-                else do-                    let size' = size + 1-                        start' = (start - 1) `rem` V.length v-                        start''-                            | start' < 0 = V.length v + start'-                            | otherwise = start'-                    V.unsafeWrite v start'' x-                    writeRef var $! DequeState v start'' size'-    {-# INLINE pushFront #-}-instance V.MVector v a => MutablePushBack (Deque v s a) where-    pushBack (Deque var) x = do-        DequeState v start size <- readRef var-        inner v start size-      where-        inner v start size = do-            if size >= V.length v-                then newVector v start size inner-                else do-                    let end = start + size-                        end'-                            | end >= V.length v = end - V.length v-                            | otherwise = end-                    V.unsafeWrite v end' x-                    writeRef var $! DequeState v start (size + 1)-    {-# INLINE pushBack #-}--newVector :: (PrimMonad m, V.MVector v a)-          => v (PrimState m) a-          -> Int-          -> Int-          -> (v (PrimState m) a -> Int -> Int -> m b)-          -> m b-newVector v size2 sizeOrig f = assert (sizeOrig == V.length v) $ do-    v' <- V.unsafeNew (V.length v * 2)-    let size1 = V.length v - size2-    V.unsafeCopy-        (V.unsafeTake size1 v')-        (V.unsafeSlice size2 size1 v)-    V.unsafeCopy-        (V.unsafeSlice size1 size2 v')-        (V.unsafeTake size2 v)-    f v' 0 sizeOrig-{-# INLINE newVector #-}
− Data/Mutable/PRef.hs 
@@ -1,64 +0,0 @@-{-# LANGUAGE MagicHash    #-}-{-# LANGUAGE TypeFamilies #-}--- | Use @ByteArray@s containing one element for mutable references.------ This is similar to @URef@s, but avoids the overhead of storing the length of--- the @Vector@, which we statically know will always be 1. This allows it to--- be a bit faster.------ Motivated by: <http://stackoverflow.com/questions/27261813/why-is-my-little-stref-int-require-allocating-gigabytes> and ArrayRef.-module Data.Mutable.PRef-    ( -- * Types-      PRef-    , IOPRef-      -- * Functions-    , asPRef-    , MutableRef (..)-    ) where--import Control.Monad            (liftM)-import Data.Mutable.Class-import Data.Primitive           (sizeOf)-import Data.Primitive.ByteArray (MutableByteArray, newByteArray, readByteArray,-                                 writeByteArray)-import Data.Primitive.Types     (Prim)-import GHC.Types                (Int (..))---- | A primitive ByteArray reference, supporting any monad.------ Since 0.2.0-newtype PRef s a = PRef (MutableByteArray s)---- |--- Since 0.2.0-asPRef :: PRef s a -> PRef s a-asPRef x = x-{-# INLINE asPRef #-}---- | A primitive ByteArray IO reference.-type IOPRef = PRef (PrimState IO)--instance MutableContainer (PRef s a) where-    type MCState (PRef s a) = s-instance Prim a => MutableRef (PRef s a) where-    type RefElement (PRef s a) = a--    newRef x = do-        ba <- newByteArray (sizeOf $! x)-        writeByteArray ba 0 x-        return $! PRef ba-    {-# INLINE newRef #-}--    readRef (PRef ba) = readByteArray ba 0-    {-# INLINE readRef #-}--    writeRef (PRef ba) = writeByteArray ba 0-    {-# INLINE writeRef #-}--    modifyRef (PRef ba) f = do-        x <- readByteArray ba 0-        writeByteArray ba 0 $! f x-    {-# INLINE modifyRef #-}--    modifyRef' = modifyRef-    {-# INLINE modifyRef' #-}
− Data/Mutable/SRef.hs 
@@ -1,55 +0,0 @@-{-# LANGUAGE TypeFamilies #-}--- | Use 1-length mutable storable vectors for mutable references.------ Motivated by: <http://stackoverflow.com/questions/27261813/why-is-my-little-stref-int-require-allocating-gigabytes> and ArrayRef.-module Data.Mutable.SRef-    ( -- * Types-      SRef-    , IOSRef-      -- * Functions-    , asSRef-    , MutableRef (..)-    ) where--import           Data.Mutable.Class-import Foreign.ForeignPtr-import Foreign.Storable-import Control.Monad.Primitive---- | A storable vector reference, supporting any monad.------ Since 0.2.0-newtype SRef s a = SRef (ForeignPtr a)---- |--- Since 0.2.0-asSRef :: SRef s a -> SRef s a-asSRef x = x-{-# INLINE asSRef #-}---- | A storable IO vector reference.-type IOSRef = SRef (PrimState IO)--instance MutableContainer (SRef s a) where-    type MCState (SRef s a) = s-instance Storable a => MutableRef (SRef s a) where-    type RefElement (SRef s a) = a--    newRef x = unsafePrimToPrim $ do-        fptr <- mallocForeignPtr-        withForeignPtr fptr $ flip poke x-        return $! SRef fptr-    {-# INLINE newRef#-}--    readRef (SRef fptr) = unsafePrimToPrim $ withForeignPtr fptr peek-    {-# INLINE readRef #-}--    writeRef (SRef fptr) x = unsafePrimToPrim $ withForeignPtr fptr $ flip poke x-    {-# INLINE writeRef #-}--    modifyRef (SRef fptr) f = unsafePrimToPrim $ withForeignPtr fptr $ \ptr ->-        peek ptr >>= poke ptr . f-    {-# INLINE modifyRef #-}--    modifyRef' = modifyRef-    {-# INLINE modifyRef' #-}
− Data/Mutable/URef.hs 
@@ -1,51 +0,0 @@-{-# LANGUAGE TypeFamilies #-}--- | Use 1-length mutable unboxed vectors for mutable references.------ Motivated by: <http://stackoverflow.com/questions/27261813/why-is-my-little-stref-int-require-allocating-gigabytes> and ArrayRef.-module Data.Mutable.URef-    ( -- * Types-      URef-    , IOURef-      -- * Functions-    , asURef-    , MutableRef (..)-    ) where--import           Control.Monad               (liftM)-import           Data.Mutable.Class-import qualified Data.Vector.Generic.Mutable as V-import qualified Data.Vector.Unboxed.Mutable as VU---- | An unboxed vector reference, supporting any monad.------ Since 0.2.0-newtype URef s a = URef (VU.MVector s a)---- |--- Since 0.2.0-asURef :: URef s a -> URef s a-asURef x = x-{-# INLINE asURef #-}---- | An unboxed IO vector reference.-type IOURef = URef (PrimState IO)--instance MutableContainer (URef s a) where-    type MCState (URef s a) = s-instance VU.Unbox a => MutableRef (URef s a) where-    type RefElement (URef s a) = a--    newRef = liftM URef . V.replicate 1-    {-# INLINE newRef#-}--    readRef (URef v) = V.unsafeRead v 0-    {-# INLINE readRef #-}--    writeRef (URef v) = V.unsafeWrite v 0-    {-# INLINE writeRef #-}--    modifyRef (URef v) f = V.unsafeRead v 0 >>= V.unsafeWrite v 0 . f-    {-# INLINE modifyRef #-}--    modifyRef' = modifyRef-    {-# INLINE modifyRef' #-}
README.md view
@@ -115,7 +115,7 @@ additional data structures: double-ended queues and doubly-linked lists. The former is based around mutable vectors, and therefore as unboxed (`UDeque`), storable (`SDeque`), and boxed (`BDeque`) variants. Doubly-linked lists have no-such variety, and are simply `DList`s.+such variety, and are simply `DLList`s.  For general purpose queue-like structures, `UDeque` or `SDeque` is likely to give you best performance. As usual, benchmark your own program to be certain,@@ -174,6 +174,7 @@ ### Deque benchmark  ```+benchmarking IORef [Int] time                 8.371 ms   (8.362 ms .. 8.382 ms)                      1.000 R²   (1.000 R² .. 1.000 R²) mean                 8.386 ms   (8.378 ms .. 8.398 ms)
bench/deque.hs view
@@ -1,7 +1,7 @@ {-# LANGUAGE ConstraintKinds #-} {-# LANGUAGE TypeFamilies    #-} import Control.Monad-import Criterion.Main+import Gauge.Main import Data.Mutable import Data.Sequence      (Seq)
bench/ref.hs view
@@ -1,6 +1,6 @@ {-# LANGUAGE TypeFamilies #-} import Control.Monad-import Criterion.Main+import Gauge.Main import Data.Mutable  test :: (MCState c ~ PrimState IO, RefElement c ~ Int, MutableRef c)
mutable-containers.cabal view
@@ -1,69 +1,100 @@-name:                mutable-containers-version:             0.3.3-synopsis:            Abstactions and concrete implementations of mutable containers-description:         See docs and README at <http://www.stackage.org/package/mutable-containers>-homepage:            https://github.com/snoyberg/mono-traversable-license:             MIT-license-file:        LICENSE-author:              Michael Snoyman-maintainer:          michael@fpcomplete.com-category:            Data-build-type:          Simple-extra-source-files:  README.md ChangeLog.md-cabal-version:       >=1.10+-- This file has been generated from package.yaml by hpack version 0.20.0.+--+-- see: https://github.com/sol/hpack+--+-- hash: 40dea8fdbd3dd312e239092feaa21012ad064fac2c05429d687759366016cfe7 +name:           mutable-containers+version:        0.3.4+synopsis:       Abstactions and concrete implementations of mutable containers+description:    See docs and README at <http://www.stackage.org/package/mutable-containers>+category:       Data+homepage:       https://github.com/snoyberg/mono-traversable#readme+bug-reports:    https://github.com/snoyberg/mono-traversable/issues+author:         Michael Snoyman+maintainer:     michael@fpcomplete.com+license:        MIT+license-file:   LICENSE+build-type:     Simple+cabal-version:  >= 1.10++extra-source-files:+    ChangeLog.md+    README.md++source-repository head+  type: git+  location: https://github.com/snoyberg/mono-traversable+ library-  exposed-modules:     Data.Mutable-  other-modules:       Data.Mutable.SRef-                       Data.Mutable.Class-                       Data.Mutable.URef-                       Data.Mutable.PRef-                       Data.Mutable.BRef-                       Data.Mutable.DLList-                       Data.Mutable.Deque-  build-depends:       base >= 4.7 && < 5-                     , primitive >= 0.5.2.1-                     , containers-                     , vector-                     , mono-traversable-                     , ghc-prim-  default-language:    Haskell2010-  ghc-options:         -O2+  hs-source-dirs:+      src+  ghc-options: -O2+  build-depends:+      base >=4.9 && <5+    , containers+    , ghc-prim+    , mono-traversable+    , primitive >=0.5.2.1+    , vector+  exposed-modules:+      Data.Mutable+  other-modules:+      Data.Mutable.BRef+      Data.Mutable.Class+      Data.Mutable.Deque+      Data.Mutable.DLList+      Data.Mutable.PRef+      Data.Mutable.SRef+      Data.Mutable.URef+      Paths_mutable_containers+  default-language: Haskell2010  test-suite test-  type:                exitcode-stdio-1.0-  hs-source-dirs:      test-  main-is:             Spec.hs-  build-depends:       base-                     , mutable-containers-                     , hspec-                     , QuickCheck-                     , vector-                     , primitive-                     , containers-  default-language:    Haskell2010+  type: exitcode-stdio-1.0+  main-is: Spec.hs+  hs-source-dirs:+      test+  build-depends:+      QuickCheck+    , base >=4.9 && <5+    , containers+    , hspec+    , mutable-containers+    , primitive+    , vector+  other-modules:+      Paths_mutable_containers+  default-language: Haskell2010  benchmark deque-  type:                exitcode-stdio-1.0-  hs-source-dirs:      bench-  main-is:             deque.hs-  build-depends:       base-                     , mutable-containers-                     , criterion-                     , containers-  ghc-options:         -Wall -O2 -rtsopts-  default-language:    Haskell2010+  type: exitcode-stdio-1.0+  main-is: deque.hs+  hs-source-dirs:+      bench+  ghc-options: -Wall -O2 -rtsopts+  build-depends:+      base >=4.9 && <5+    , containers+    , gauge+    , mutable-containers+    , vector+  other-modules:+      Paths_mutable_containers+  default-language: Haskell2010  benchmark ref-  type:                exitcode-stdio-1.0-  hs-source-dirs:      bench-  main-is:             ref.hs-  build-depends:       base-                     , mutable-containers-                     , criterion-  ghc-options:         -Wall -O2 -rtsopts-  default-language:    Haskell2010--source-repository head-  type:     git-  location: https://github.com/snoyberg/mono-traversable.git+  type: exitcode-stdio-1.0+  main-is: ref.hs+  hs-source-dirs:+      bench+  ghc-options: -Wall -O2 -rtsopts+  build-depends:+      base >=4.9 && <5+    , containers+    , gauge+    , mutable-containers+    , vector+  other-modules:+      Paths_mutable_containers+  default-language: Haskell2010
+ src/Data/Mutable.hs view
@@ -0,0 +1,68 @@+-- | Classes and concrete implementations for mutable data structures.+--+-- For more information on the design of this library, see the README file,+-- also available at <http://www.stackage.org/package/mutable-containers>.+module Data.Mutable+    ( -- * Data types+      -- ** Single-cell mutable references+      PRef+    , IOPRef+    , asPRef+    , URef+    , IOURef+    , asURef+    , SRef+    , IOSRef+    , asSRef+    , BRef+    , IOBRef+    , asBRef+      -- *** Standard re-exports+    , IORef+    , asIORef+    , STRef+    , asSTRef+    , MutVar+    , asMutVar+      -- ** Collections/queues+    , Deque+    , UDeque+    , asUDeque+    , SDeque+    , asSDeque+    , BDeque+    , asBDeque+    , DLList+    , asDLList+      -- * Type classes+    , MutableContainer (..)+    , MutableRef (..)+    , MutableAtomicRef (..)+    , MutableCollection (..)+    , MutablePushFront (..)+    , MutablePushBack (..)+    , MutablePopFront (..)+    , MutablePopBack (..)+      -- * Constraint kinds+    , MutableQueue+    , MutableStack+    , MutableDeque+      -- * Convenience re-exports+    , PrimMonad+    , PrimState+    , RealWorld+    , Prim+    , Unbox+    , Storable+    ) where++import Data.Mutable.Class+import Data.Mutable.URef+import Data.Mutable.SRef+import Data.Mutable.PRef+import Data.Mutable.BRef+import Data.Mutable.Deque+import Data.Mutable.DLList+import Data.Vector.Unboxed (Unbox)+import Data.Primitive (Prim)+import Data.Vector.Storable (Storable)
+ src/Data/Mutable/BRef.hs view
@@ -0,0 +1,71 @@+{-# LANGUAGE TypeFamilies #-}+-- | Use 1-length mutable boxed vectors for mutable references.+--+-- Motivated by: <http://stackoverflow.com/questions/27261813/why-is-my-little-stref-int-require-allocating-gigabytes> and ArrayRef.+module Data.Mutable.BRef+    ( -- * Types+      BRef+    , IOBRef+      -- * Functions+    , asBRef+    , MutableRef (..)+    ) where++import           Control.Monad               (liftM)+import           Data.Monoid                 (Monoid, mempty)+import           Data.MonoTraversable        (Element)+import           Data.Mutable.Class+import           Data.Sequences              (IsSequence)+import qualified Data.Vector.Generic.Mutable as V+import qualified Data.Vector.Mutable         as VB++-- | A boxed vector reference, supporting any monad.+--+-- Since 0.2.0+newtype BRef s a = BRef (VB.MVector s a)++-- |+-- Since 0.2.0+asBRef :: BRef s a -> BRef s a+asBRef x = x+{-# INLINE asBRef #-}++-- | A boxed IO vector reference.+type IOBRef = BRef (PrimState IO)++instance MutableContainer (BRef s a) where+    type MCState (BRef s a) = s+instance MutableRef (BRef s a) where+    type RefElement (BRef s a) = a++    newRef = liftM BRef . V.replicate 1+    {-# INLINE newRef#-}++    readRef (BRef v) = V.unsafeRead v 0+    {-# INLINE readRef #-}++    writeRef (BRef v) = V.unsafeWrite v 0+    {-# INLINE writeRef #-}++    modifyRef (BRef v) f = V.unsafeRead v 0 >>= V.unsafeWrite v 0 . f+    {-# INLINE modifyRef #-}++    modifyRef' = modifyRef+    {-# INLINE modifyRef' #-}++instance Monoid w => MutableCollection (BRef s w) where+    type CollElement (BRef s w) = Element w+    newColl = newRef mempty+    {-# INLINE newColl #-}+instance IsSequence seq => MutablePushFront (BRef s seq) where+    pushFront = pushFrontRef+    {-# INLINE pushFront #-}+instance IsSequence seq => MutablePushBack (BRef s seq) where+    pushBack = pushBackRef+    {-# INLINE pushBack #-}+instance IsSequence seq => MutablePopFront (BRef s seq) where+    popFront = popFrontRef+    {-# INLINE popFront #-}+instance IsSequence seq => MutablePopBack (BRef s seq) where+    popBack = popBackRef+    {-# INLINE popBack #-}
+ src/Data/Mutable/Class.hs view
@@ -0,0 +1,373 @@+{-# LANGUAGE ConstraintKinds   #-}+{-# LANGUAGE FlexibleContexts  #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE TypeFamilies      #-}+-- | Various typeclasses for mutable containers.+module Data.Mutable.Class+    ( PrimMonad+    , PrimState+    , RealWorld+    , MutableQueue+    , MutableStack+    , MutableDeque+    , IORef+    , asIORef+    , STRef+    , asSTRef+    , MutVar+    , asMutVar+    , MutableContainer (..)+    , MutableRef (..)+    , MutableAtomicRef (..)+    , MutableCollection (..)+    , MutablePushFront (..)+    , MutablePushBack (..)+    , MutablePopFront (..)+    , MutablePopBack (..)+    , pushFrontRef+    , pushBackRef+    , popFrontRef+    , popBackRef+    ) where++import           Control.Monad.Primitive+import           Data.IORef+import           Data.Monoid+import           Data.MonoTraversable    (Element)+import           Data.Primitive.MutVar+import qualified Data.Sequences          as Seqs+import           Data.STRef++-- | The parent typeclass for all mutable containers.+--+-- Since 0.2.0+class MutableContainer c where+    -- | Associated type giving the primitive state token for the given+    -- container, much like 'PrimState' from primitive.+    --+    -- Since 0.2.0+    type MCState c++instance MutableContainer (IORef a) where+    type MCState (IORef a) = PrimState IO+instance MutableContainer (STRef s a) where+    type MCState (STRef s a) = s+instance MutableContainer (MutVar s a) where+    type MCState (MutVar s a) = s++-- | Typeclass for single-cell mutable references.+--+-- Since 0.2.0+class MutableContainer c => MutableRef c where+    -- | Associated type giving the type of the value inside the mutable+    -- reference.+    --+    -- Since 0.2.0+    type RefElement c++    -- | Create a new mutable reference with the given value.+    --+    -- Since 0.2.0+    newRef :: (PrimMonad m, PrimState m ~ MCState c)+           => RefElement c+           -> m c++    -- | Read the current value in the mutable reference.+    --+    -- Since 0.2.0+    readRef :: (PrimMonad m, PrimState m ~ MCState c)+            => c+            -> m (RefElement c)++    -- | Write a new value to the mutable reference.+    --+    -- Since 0.2.0+    writeRef :: (PrimMonad m, PrimState m ~ MCState c)+             => c+             -> RefElement c+             -> m ()++    -- | Modify the value in the mutable reference, without necessarily forcing the result.+    --+    -- Note: some implementations /will/ force the result, in particular+    -- @PRef@, @SRef@, and @URef@.+    --+    -- Since 0.2.0+    modifyRef :: (PrimMonad m, PrimState m ~ MCState c)+              => c+              -> (RefElement c -> RefElement c)+              -> m ()++    -- | Modify the value in the mutable reference, forcing the result.+    --+    -- Since 0.2.0+    modifyRef' :: (PrimMonad m, PrimState m ~ MCState c)+               => c+               -> (RefElement c -> RefElement c)+               -> m ()++instance MutableRef (IORef a) where+    type RefElement (IORef a) = a+    newRef = primToPrim . newIORef+    {-# INLINE newRef #-}+    readRef = primToPrim . readIORef+    {-# INLINE readRef #-}+    writeRef c = primToPrim . writeIORef c+    {-# INLINE writeRef #-}+    modifyRef c = primToPrim . modifyIORef c+    {-# INLINE modifyRef #-}+    modifyRef' c = primToPrim . modifyIORef' c+    {-# INLINE modifyRef' #-}+instance MutableRef (STRef s a) where+    type RefElement (STRef s a) = a+    newRef = primToPrim . newSTRef+    {-# INLINE newRef #-}+    readRef = primToPrim . readSTRef+    {-# INLINE readRef #-}+    writeRef c = primToPrim . writeSTRef c+    {-# INLINE writeRef #-}+    modifyRef c = primToPrim . modifySTRef c+    {-# INLINE modifyRef #-}+    modifyRef' c = primToPrim . modifySTRef' c+    {-# INLINE modifyRef' #-}+instance MutableRef (MutVar s a) where+    type RefElement (MutVar s a) = a+    newRef = newMutVar+    {-# INLINE newRef #-}+    readRef = readMutVar+    {-# INLINE readRef #-}+    writeRef = writeMutVar+    {-# INLINE writeRef #-}+    modifyRef = modifyMutVar+    {-# INLINE modifyRef #-}+    modifyRef' = modifyMutVar'+    {-# INLINE modifyRef' #-}++-- | @MutableRef@s that provide for atomic modifications of their contents.+--+-- Since 0.2.0+class MutableRef c => MutableAtomicRef c where+    -- | Modify the value without necessarily forcing the result.+    --+    -- Since 0.2.0+    atomicModifyRef+        :: (PrimMonad m, PrimState m ~ MCState c)+        => c+        -> (RefElement c -> (RefElement c, a))+        -> m a++    -- | Modify the value, forcing the result.+    --+    -- Since 0.2.0+    atomicModifyRef'+        :: (PrimMonad m, PrimState m ~ MCState c)+        => c+        -> (RefElement c -> (RefElement c, a))+        -> m a+instance MutableAtomicRef (IORef a) where+    atomicModifyRef c = primToPrim . atomicModifyIORef c+    {-# INLINE atomicModifyRef #-}+    atomicModifyRef' c = primToPrim . atomicModifyIORef' c+    {-# INLINE atomicModifyRef' #-}+instance MutableAtomicRef (MutVar s a) where+    atomicModifyRef = atomicModifyMutVar+    {-# INLINE atomicModifyRef #-}+    atomicModifyRef' = atomicModifyMutVar'+    {-# INLINE atomicModifyRef' #-}++-- | Containers which contain 0 or more values.+--+-- Since 0.2.0+class MutableContainer c => MutableCollection c where+    -- | The type of each value in the collection.+    --+    -- Since 0.2.0+    type CollElement c++    -- | Create a new, empty collection.+    --+    -- Since 0.2.0+    newColl :: (PrimMonad m, PrimState m ~ MCState c)+            => m c+instance Data.Monoid.Monoid w => MutableCollection (IORef w) where+    type CollElement (IORef w) = Element w+    newColl = newRef mempty+    {-# INLINE newColl #-}+instance Monoid w => MutableCollection (STRef s w) where+    type CollElement (STRef s w) = Element w+    newColl = newRef mempty+    {-# INLINE newColl #-}+instance Monoid w => MutableCollection (MutVar s w) where+    type CollElement (MutVar s w) = Element w+    newColl = newRef mempty+    {-# INLINE newColl #-}++-- | Take a value from the front of the collection, if available.+--+-- Since 0.2.0+class MutableCollection c => MutablePopFront c where+    -- | Take a value from the front of the collection, if available.+    --+    -- Since 0.2.0+    popFront :: (PrimMonad m, PrimState m ~ MCState c)+             => c+             -> m (Maybe (CollElement c))+popFrontRef+    :: ( PrimMonad m+       , PrimState m ~ MCState c+       , MutableRef c+       , CollElement c ~ Element (RefElement c)+       , Seqs.IsSequence (RefElement c)+       )+    => c+    -> m (Maybe (CollElement c))+popFrontRef c = do+    l <- readRef c+    case Seqs.uncons l of+        Nothing -> return Nothing+        Just (x, xs) -> do+            writeRef c xs+            return (Just x)+{-# INLINE popFrontRef #-}+instance Seqs.IsSequence a => MutablePopFront (IORef a) where+    popFront = popFrontRef+    {-# INLINE popFront #-}+instance Seqs.IsSequence a => MutablePopFront (STRef s a) where+    popFront = popFrontRef+    {-# INLINE popFront #-}+instance Seqs.IsSequence a => MutablePopFront (MutVar s a) where+    popFront = popFrontRef+    {-# INLINE popFront #-}++-- | Place a value at the front of the collection.+--+-- Since 0.2.0+class MutableCollection c => MutablePushFront c where+    -- | Place a value at the front of the collection.+    --+    -- Since 0.2.0+    pushFront :: (PrimMonad m, PrimState m ~ MCState c)+              => c+              -> CollElement c+              -> m ()+pushFrontRef+    :: ( PrimMonad m+       , PrimState m ~ MCState c+       , MutableRef c+       , CollElement c ~ Element (RefElement c)+       , Seqs.IsSequence (RefElement c)+       )+    => c+    -> CollElement c+    -> m ()+pushFrontRef c e = modifyRef' c (Seqs.cons e)+{-# INLINE pushFrontRef #-}+instance Seqs.IsSequence a => MutablePushFront (IORef a) where+    pushFront = pushFrontRef+    {-# INLINE pushFront #-}+instance Seqs.IsSequence a => MutablePushFront (STRef s a) where+    pushFront = pushFrontRef+    {-# INLINE pushFront #-}+instance Seqs.IsSequence a => MutablePushFront (MutVar s a) where+    pushFront = pushFrontRef+    {-# INLINE pushFront #-}++-- | Take a value from the back of the collection, if available.+--+-- Since 0.2.0+class MutableCollection c => MutablePopBack c where+    -- | Take a value from the back of the collection, if available.+    --+    -- Since 0.2.0+    popBack :: (PrimMonad m, PrimState m ~ MCState c)+            => c+            -> m (Maybe (CollElement c))+popBackRef+    :: ( PrimMonad m+       , PrimState m ~ MCState c+       , MutableRef c+       , CollElement c ~ Element (RefElement c)+       , Seqs.IsSequence (RefElement c)+       )+    => c+    -> m (Maybe (CollElement c))+popBackRef c = do+    l <- readRef c+    case Seqs.unsnoc l of+        Nothing -> return Nothing+        Just (xs, x) -> do+            writeRef c xs+            return (Just x)+{-# INLINE popBackRef #-}+instance Seqs.IsSequence a => MutablePopBack (IORef a) where+    popBack = popBackRef+    {-# INLINE popBack #-}+instance Seqs.IsSequence a => MutablePopBack (STRef s a) where+    popBack = popBackRef+    {-# INLINE popBack #-}+instance Seqs.IsSequence a => MutablePopBack (MutVar s a) where+    popBack = popBackRef+    {-# INLINE popBack #-}++-- | Place a value at the back of the collection.+--+-- Since 0.2.0+class MutableCollection c => MutablePushBack c where+    -- | Place a value at the back of the collection.+    --+    -- Since 0.2.0+    pushBack :: (PrimMonad m, PrimState m ~ MCState c)+             => c+             -> CollElement c+             -> m ()+pushBackRef+    :: ( PrimMonad m+       , PrimState m ~ MCState c+       , MutableRef c+       , CollElement c ~ Element (RefElement c)+       , Seqs.IsSequence (RefElement c)+       )+    => c+    -> CollElement c+    -> m ()+pushBackRef c e = modifyRef' c (`Seqs.snoc` e)+{-# INLINE pushBackRef #-}+instance Seqs.IsSequence a => MutablePushBack (IORef a) where+    pushBack = pushBackRef+    {-# INLINE pushBack #-}+instance Seqs.IsSequence a => MutablePushBack (STRef s a) where+    pushBack = pushBackRef+    {-# INLINE pushBack #-}+instance Seqs.IsSequence a => MutablePushBack (MutVar s a) where+    pushBack = pushBackRef+    {-# INLINE pushBack #-}++-- | Collections which allow pushing and popping at the front (aka FIFOs).+--+-- Since 0.2.0+type MutableQueue c = (MutablePopFront c, MutablePushBack c)++-- | Collections which allow pushing at the back and popping at the front (aka FILOs).+--+-- Since 0.2.0+type MutableStack c = (MutablePopFront c, MutablePushFront c)++-- | Collections which allow pushing and popping at the front and back.+--+-- Since 0.2.0+type MutableDeque c = (MutableQueue c, MutablePushFront c, MutablePopBack c)++-- |+-- Since 0.2.0+asIORef :: IORef a -> IORef a+asIORef = id++-- |+-- Since 0.2.0+asSTRef :: STRef s a -> STRef s a+asSTRef = id++-- |+-- Since 0.2.0+asMutVar :: MutVar s a -> MutVar s a+asMutVar = id
+ src/Data/Mutable/DLList.hs view
@@ -0,0 +1,101 @@+{-# LANGUAGE TypeFamilies #-}+-- | Doubly-linked list+module Data.Mutable.DLList+    ( DLList+    , asDLList+    , module Data.Mutable.Class+    ) where++import Data.Mutable.Class++data Node s a = Node+    a+    (MutVar s (Maybe (Node s a))) -- previous+    (MutVar s (Maybe (Node s a))) -- next++-- | A doubly-linked list.+--+-- Since 0.3.0+data DLList s a = DLList (MutVar s (Maybe (Node s a))) (MutVar s (Maybe (Node s a)))++-- |+-- Since 0.2.0+asDLList :: DLList s a -> DLList s a+asDLList = id+{-# INLINE asDLList #-}++instance MutableContainer (DLList s a) where+    type MCState (DLList s a) = s+instance MutableCollection (DLList s a) where+    type CollElement (DLList s a) = a+    newColl = do+        x <- newRef $! Nothing+        y <- newRef $! Nothing+        return $! DLList x y+    {-# INLINE newColl #-}+instance MutablePopFront (DLList s a) where+    popFront (DLList frontRef backRef) = do+        mfront <- readRef frontRef+        case mfront of+            Nothing -> return Nothing+            Just (Node val _ nextRef) -> do+                mnext <- readRef nextRef+                case mnext of+                    Nothing -> do+                        writeRef frontRef $! Nothing+                        writeRef backRef $! Nothing+                    Just next@(Node _ prevRef _) -> do+                        writeRef prevRef $! Nothing+                        writeRef frontRef $! Just next+                return $ Just val+    {-# INLINE popFront #-}+instance MutablePopBack (DLList s a) where+    popBack (DLList frontRef backRef) = do+        mback <- readRef backRef+        case mback of+            Nothing -> return Nothing+            Just (Node val prevRef _) -> do+                mprev <- readRef prevRef+                case mprev of+                    Nothing -> do+                        writeRef frontRef $! Nothing+                        writeRef backRef $! Nothing+                    Just prev@(Node _ _ nextRef) -> do+                        writeRef nextRef $! Nothing+                        writeRef backRef (Just prev)+                return $ Just val+    {-# INLINE popBack #-}+instance MutablePushFront (DLList s a) where+    pushFront (DLList frontRef backRef) val = do+        mfront <- readRef frontRef+        case mfront of+            Nothing -> do+                prevRef <- newRef $! Nothing+                nextRef <- newRef $! Nothing+                let node = Just $ Node val prevRef nextRef+                writeRef frontRef node+                writeRef backRef node+            Just front@(Node _ prevRef _) -> do+                prevRefNew <- newRef $! Nothing+                nextRef <- newRef $ Just front+                let node = Just $ Node val prevRefNew nextRef+                writeRef prevRef node+                writeRef frontRef node+    {-# INLINE pushFront #-}+instance MutablePushBack (DLList s a) where+    pushBack (DLList frontRef backRef) val = do+        mback <- readRef backRef+        case mback of+            Nothing -> do+                prevRef <- newRef $! Nothing+                nextRef <- newRef $! Nothing+                let node = Just $! Node val prevRef nextRef+                writeRef frontRef $! node+                writeRef backRef $! node+            Just back@(Node _ _ nextRef) -> do+                nextRefNew <- newRef $! Nothing+                prevRef <- newRef $! Just back+                let node = Just $! Node val prevRef nextRefNew+                writeRef nextRef $! node+                writeRef backRef $! node+    {-# INLINE pushBack #-}
+ src/Data/Mutable/Deque.hs view
@@ -0,0 +1,152 @@+{-# LANGUAGE TypeFamilies #-}+module Data.Mutable.Deque+    ( Deque+    , UDeque+    , asUDeque+    , SDeque+    , asSDeque+    , BDeque+    , asBDeque+    , module Data.Mutable.Class+    ) where++import           Control.Exception            (assert)+import           Control.Monad                (liftM)+import           Data.Mutable.Class+import qualified Data.Vector.Generic.Mutable  as V+import qualified Data.Vector.Mutable          as B+import qualified Data.Vector.Storable.Mutable as S+import qualified Data.Vector.Unboxed.Mutable  as U++data DequeState v s a = DequeState+    (v s a)+    {-# UNPACK #-} !Int -- start+    {-# UNPACK #-} !Int -- size++-- | A double-ended queue supporting any underlying vector type and any monad.+--+-- This implements a circular double-ended queue with exponential growth.+--+-- Since 0.2.0+newtype Deque v s a = Deque (MutVar s (DequeState v s a))++-- | A 'Deque' specialized to unboxed vectors.+--+-- Since 0.2.0+type UDeque = Deque U.MVector++-- | A 'Deque' specialized to storable vectors.+--+-- Since 0.2.0+type SDeque = Deque S.MVector++-- | A 'Deque' specialized to boxed vectors.+--+-- Since 0.2.0+type BDeque = Deque B.MVector++-- |+-- Since 0.2.0+asUDeque :: UDeque s a -> UDeque s a+asUDeque = id++-- |+-- Since 0.2.0+asSDeque :: SDeque s a -> SDeque s a+asSDeque = id++-- |+-- Since 0.2.0+asBDeque :: BDeque s a -> BDeque s a+asBDeque = id++instance MutableContainer (Deque v s a) where+    type MCState (Deque v s a) = s+instance V.MVector v a => MutableCollection (Deque v s a) where+    type CollElement (Deque v s a) = a+    newColl = do+        v <- V.new baseSize+        liftM Deque $ newRef (DequeState v 0 0)+      where+        baseSize = 32+    {-# INLINE newColl #-}+instance V.MVector v a => MutablePopFront (Deque v s a) where+    popFront (Deque var) = do+        DequeState v start size <- readRef var+        if size == 0+            then return Nothing+            else do+                x <- V.unsafeRead v start+                let start' = start + 1+                    start''+                        | start' >= V.length v = 0+                        | otherwise = start'+                writeRef var $! DequeState v start'' (size - 1)+                return $! Just x+    {-# INLINE popFront #-}+instance V.MVector v a => MutablePopBack (Deque v s a) where+    popBack (Deque var) = do+        DequeState v start size <- readRef var+        if size == 0+            then return Nothing+            else do+                let size' = size - 1+                    end = start + size'+                    end'+                        | end >= V.length v = end - V.length v+                        | otherwise = end+                x <- V.unsafeRead v end'+                writeRef var $! DequeState v start size'+                return $! Just x+    {-# INLINE popBack #-}+instance V.MVector v a => MutablePushFront (Deque v s a) where+    pushFront (Deque var) x = do+        DequeState v start size <- readRef var+        inner v start size+      where+        inner v start size = do+            if size >= V.length v+                then newVector v start size inner+                else do+                    let size' = size + 1+                        start' = (start - 1) `rem` V.length v+                        start''+                            | start' < 0 = V.length v + start'+                            | otherwise = start'+                    V.unsafeWrite v start'' x+                    writeRef var $! DequeState v start'' size'+    {-# INLINE pushFront #-}+instance V.MVector v a => MutablePushBack (Deque v s a) where+    pushBack (Deque var) x = do+        DequeState v start size <- readRef var+        inner v start size+      where+        inner v start size = do+            if size >= V.length v+                then newVector v start size inner+                else do+                    let end = start + size+                        end'+                            | end >= V.length v = end - V.length v+                            | otherwise = end+                    V.unsafeWrite v end' x+                    writeRef var $! DequeState v start (size + 1)+    {-# INLINE pushBack #-}++newVector :: (PrimMonad m, V.MVector v a)+          => v (PrimState m) a+          -> Int+          -> Int+          -> (v (PrimState m) a -> Int -> Int -> m b)+          -> m b+newVector v size2 sizeOrig f = assert (sizeOrig == V.length v) $ do+    v' <- V.unsafeNew (V.length v * 2)+    let size1 = V.length v - size2+    V.unsafeCopy+        (V.unsafeTake size1 v')+        (V.unsafeSlice size2 size1 v)+    V.unsafeCopy+        (V.unsafeSlice size1 size2 v')+        (V.unsafeTake size2 v)+    f v' 0 sizeOrig+{-# INLINE newVector #-}
+ src/Data/Mutable/PRef.hs view
@@ -0,0 +1,62 @@+{-# LANGUAGE MagicHash    #-}+{-# LANGUAGE TypeFamilies #-}+-- | Use @ByteArray@s containing one element for mutable references.+--+-- This is similar to @URef@s, but avoids the overhead of storing the length of+-- the @Vector@, which we statically know will always be 1. This allows it to+-- be a bit faster.+--+-- Motivated by: <http://stackoverflow.com/questions/27261813/why-is-my-little-stref-int-require-allocating-gigabytes> and ArrayRef.+module Data.Mutable.PRef+    ( -- * Types+      PRef+    , IOPRef+      -- * Functions+    , asPRef+    , MutableRef (..)+    ) where++import Data.Mutable.Class+import Data.Primitive           (sizeOf)+import Data.Primitive.ByteArray (MutableByteArray, newByteArray, readByteArray,+                                 writeByteArray)+import Data.Primitive.Types     (Prim)++-- | A primitive ByteArray reference, supporting any monad.+--+-- Since 0.2.0+newtype PRef s a = PRef (MutableByteArray s)++-- |+-- Since 0.2.0+asPRef :: PRef s a -> PRef s a+asPRef x = x+{-# INLINE asPRef #-}++-- | A primitive ByteArray IO reference.+type IOPRef = PRef (PrimState IO)++instance MutableContainer (PRef s a) where+    type MCState (PRef s a) = s+instance Prim a => MutableRef (PRef s a) where+    type RefElement (PRef s a) = a++    newRef x = do+        ba <- newByteArray (sizeOf $! x)+        writeByteArray ba 0 x+        return $! PRef ba+    {-# INLINE newRef #-}++    readRef (PRef ba) = readByteArray ba 0+    {-# INLINE readRef #-}++    writeRef (PRef ba) = writeByteArray ba 0+    {-# INLINE writeRef #-}++    modifyRef (PRef ba) f = do+        x <- readByteArray ba 0+        writeByteArray ba 0 $! f x+    {-# INLINE modifyRef #-}++    modifyRef' = modifyRef+    {-# INLINE modifyRef' #-}
+ src/Data/Mutable/SRef.hs view
@@ -0,0 +1,55 @@+{-# LANGUAGE TypeFamilies #-}+-- | Use 1-length mutable storable vectors for mutable references.+--+-- Motivated by: <http://stackoverflow.com/questions/27261813/why-is-my-little-stref-int-require-allocating-gigabytes> and ArrayRef.+module Data.Mutable.SRef+    ( -- * Types+      SRef+    , IOSRef+      -- * Functions+    , asSRef+    , MutableRef (..)+    ) where++import           Data.Mutable.Class+import Foreign.ForeignPtr+import Foreign.Storable+import Control.Monad.Primitive++-- | A storable vector reference, supporting any monad.+--+-- Since 0.2.0+newtype SRef s a = SRef (ForeignPtr a)++-- |+-- Since 0.2.0+asSRef :: SRef s a -> SRef s a+asSRef x = x+{-# INLINE asSRef #-}++-- | A storable IO vector reference.+type IOSRef = SRef (PrimState IO)++instance MutableContainer (SRef s a) where+    type MCState (SRef s a) = s+instance Storable a => MutableRef (SRef s a) where+    type RefElement (SRef s a) = a++    newRef x = unsafePrimToPrim $ do+        fptr <- mallocForeignPtr+        withForeignPtr fptr $ flip poke x+        return $! SRef fptr+    {-# INLINE newRef#-}++    readRef (SRef fptr) = unsafePrimToPrim $ withForeignPtr fptr peek+    {-# INLINE readRef #-}++    writeRef (SRef fptr) x = unsafePrimToPrim $ withForeignPtr fptr $ flip poke x+    {-# INLINE writeRef #-}++    modifyRef (SRef fptr) f = unsafePrimToPrim $ withForeignPtr fptr $ \ptr ->+        peek ptr >>= poke ptr . f+    {-# INLINE modifyRef #-}++    modifyRef' = modifyRef+    {-# INLINE modifyRef' #-}
+ src/Data/Mutable/URef.hs view
@@ -0,0 +1,51 @@+{-# LANGUAGE TypeFamilies #-}+-- | Use 1-length mutable unboxed vectors for mutable references.+--+-- Motivated by: <http://stackoverflow.com/questions/27261813/why-is-my-little-stref-int-require-allocating-gigabytes> and ArrayRef.+module Data.Mutable.URef+    ( -- * Types+      URef+    , IOURef+      -- * Functions+    , asURef+    , MutableRef (..)+    ) where++import           Control.Monad               (liftM)+import           Data.Mutable.Class+import qualified Data.Vector.Generic.Mutable as V+import qualified Data.Vector.Unboxed.Mutable as VU++-- | An unboxed vector reference, supporting any monad.+--+-- Since 0.2.0+newtype URef s a = URef (VU.MVector s a)++-- |+-- Since 0.2.0+asURef :: URef s a -> URef s a+asURef x = x+{-# INLINE asURef #-}++-- | An unboxed IO vector reference.+type IOURef = URef (PrimState IO)++instance MutableContainer (URef s a) where+    type MCState (URef s a) = s+instance VU.Unbox a => MutableRef (URef s a) where+    type RefElement (URef s a) = a++    newRef = liftM URef . V.replicate 1+    {-# INLINE newRef#-}++    readRef (URef v) = V.unsafeRead v 0+    {-# INLINE readRef #-}++    writeRef (URef v) = V.unsafeWrite v 0+    {-# INLINE writeRef #-}++    modifyRef (URef v) f = V.unsafeRead v 0 >>= V.unsafeWrite v 0 . f+    {-# INLINE modifyRef #-}++    modifyRef' = modifyRef+    {-# INLINE modifyRef' #-}