value-supply 0.4 → 0.5

raw patch · 2 files changed

+91/−88 lines, 2 files

Files

Data/Supply.hs +88/−87
value-supply.cabal +3/−1

Data/Supply.hs view

@@ -21,14 +21,15 @@   , newSupply   , newEnumSupply   , newNumSupply-  , unsafeNewIntSupply +  , newDupableSupply+  , newDupableEnumSupply+  , newDupableNumSupply+   -- * Obtaining values from supplies   , supplyValue    -- * Generating new supplies from old-  , supplyLeft-  , supplyRight   , modifySupply   , split   , split2@@ -36,105 +37,100 @@   , split4   ) where --- Usinga an IORef is thread-safe because we update it with 'atomicModifyIORef'.--- XXX: Is the atomic necessary?-import Data.IORef(IORef,newIORef,atomicModifyIORef)-import System.IO.Unsafe(unsafePerformIO,unsafeInterleaveIO)+-- NOTE: Using an IORef is thread-safe because we update it with+-- 'atomicModifyIORef'.  We need the 'atomicModifyRef' because multiple+-- threads may be evaluating different supplies that share the same+-- 'IORef' and we need to avoid race conditions.  This is the case for+-- both the normal and the dupable supplies.+import Data.IORef(newIORef,atomicModifyIORef)+import System.IO.Unsafe(unsafeInterleaveIO)  #if __GLASGOW_HASKELL__ >= 608-import GHC.IOBase(unsafeDupableInterleaveIO,unsafeDupablePerformIO)+import GHC.IOBase(unsafeDupableInterleaveIO) #else unsafeDupableInterleaveIO :: IO a -> IO a unsafeDupableInterleaveIO = unsafeInterleaveIO--unsafeDupablePerformIO :: IO a -> a-unsafeDupablePerformIO = unsafePerformIO #endif  -- Basics ----------------------------------------------------------------------  -- | A type that can be used to generate values on demand.--- A supply may be turned into two different supplies by using--- the functions 'supplyLeft' and 'supplyRight'.-data Supply a = Node-  { -- | Get the value of a supply.  This function, together with-    -- 'modifySupply' forms a comonad on 'Supply'.-    supplyValue :: a+data Supply a = Node a (Supply a) (Supply a) -  -- | Generate a new supply.  This supply is different from the one-  -- generated with 'supplyRight'.-  , supplyLeft  :: Supply a+-- | Get the value of a supply.  This function, together with+-- 'modifySupply' forms a comonad on 'Supply'.+supplyValue    :: Supply a -> a+supplyValue (Node a _ _) = a -  -- | Generate a new supply. This supply is different from the one-  -- generated with 'supplyLeft'.-  , supplyRight :: Supply a-  }+-- | Generate an infinite list of supplies.+split          :: Supply a -> [Supply a]+split (Node _ s1 s2)  = s1 : split s2 +-- | Split a supply into two different supplies.+-- The resulting supplies are different from the input supply.+split2         :: Supply a -> (Supply a, Supply a)+split2 (Node _ s1 s2) = (s1,s2)++-- | Split a supply into three different supplies.+split3         :: Supply a -> (Supply a, Supply a, Supply a)+split3 (Node _ s1 (Node _ s2 s3)) = (s1,s2,s3)++-- | Split a supply into four different supplies.+split4         :: Supply a -> (Supply a, Supply a, Supply a, Supply a)+split4 (Node _ s1 (Node _ s2 (Node _ s3 s4))) = (s1,s2,s3,s4)++++ instance Functor Supply where   fmap f s = modifySupply s (f . supplyValue)  -{-# INLINE genericNewSupply #-}-genericNewSupply :: b -> (IORef b -> IO a) -> IO (Supply a)-genericNewSupply start genSym = gen =<< newIORef start-  where gen r = unsafeInterleaveIO-              $ do ls <- gen r-                   rs <- gen r-                   return (Node (unsafePerformIO (genSym r)) ls rs)- -- | Creates a new supply of values. -- The arguments specify how to generate values: -- the first argument is an initial value, the -- second specifies how to generate a new value from an existing one.-newSupply      :: a -> (a -> a) -> IO (Supply a)-newSupply x f   = genericNewSupply (iterate f x) listGenSym+{-# INLINE newSupply #-}+newSupply :: a -> (a -> a) -> IO (Supply a)+newSupply start next = gen =<< newIORef start+  where gen r = unsafeInterleaveIO+              $ do v  <- unsafeInterleaveIO (atomicModifyIORef r upd)+                   ls <- gen r+                   rs <- gen r+                   return (Node v ls rs)+        upd a = let b = next a in seq b (b, a) -{-# SPECIALIZE newEnumSupply :: IO (Supply Int) #-}--- | A supply of values that are in the 'Enum' class.--- The initial value is @toEnum 0@, new values are generates with 'succ'.-newEnumSupply  :: (Enum a) => IO (Supply a)-newEnumSupply   = genericNewSupply (toEnum 0) enumGenSym -{-# SPECIALIZE newNumSupply :: IO (Supply Int) #-}--- | A supply of values that are in the 'Num' class.--- The initial value is 0, new values are generated by adding 1.-newNumSupply   :: (Num a) => IO (Supply a)-newNumSupply    = genericNewSupply 0 numGenSym---- | Create a supply of ints.--- WARNING: In general, this is not thread safe!--- It should be OK, as long as the supply is not accessed by different threads.--- So, if you are in a multi-threaded setting, first split--- the supply, and give /different/ supply values to the different threads.-unsafeNewIntSupply :: IO (Supply Int)-unsafeNewIntSupply = gen =<< newIORef 0+-- | Create a new supply of values.+-- WARNING: This version is faster then 'newSupply' but it is not completely+-- thread safe, so use only if performance is an issue!+--+-- Rules for using the generated supplies:+--   * Supply splitting should be evaluated in a single thread.+--     For example, use "case" with 'split2' to force the splitting+--     of a supply.+--   * Different threads should work with different supplies.+--     For example, one could (strictly) split a supply, and then+--     fork new threads with the resulting supplies.+{-# INLINE newDupableSupply #-}+newDupableSupply :: a -> (a -> a) -> IO (Supply a)+newDupableSupply start next = gen =<< newIORef start   where gen r = unsafeDupableInterleaveIO-              $ do ls <- gen r+              $ do v  <- unsafeDupableInterleaveIO (atomicModifyIORef r upd)+                   ls <- gen r                    rs <- gen r-                   return (Node (unsafeDupablePerformIO (enumGenSym r)) ls rs)--+                   return (Node v ls rs)+        upd a = let b = next a in seq b (b, a)  --- Different ways to generate new values:-listGenSym     :: IORef [a] -> IO a-listGenSym r    = atomicModifyIORef r (\(a:as) -> (as,a))--enumGenSym     :: Enum a => IORef a -> IO a-enumGenSym r    = atomicModifyIORef r (\a -> let n = succ a in seq n (n,a))--numGenSym      :: Num a => IORef a -> IO a-numGenSym r     = atomicModifyIORef r (\a -> let n = 1 + a in seq n (n,a))-+-- XXX: Is the strictness of 'modifySupply' OK?  -- | Generate a new supply by systematically applying a function -- to an existing supply.  This function, together with 'supplyValue' -- form a comonad on 'Supply'. modifySupply :: Supply a -> (Supply a -> b) -> Supply b-modifySupply s f = Node { supplyValue = f s-                        , supplyLeft  = modifySupply (supplyLeft s) f-                        , supplyRight = modifySupply (supplyRight s) f-                        }+modifySupply s f = Node (f s) (modifySupply l f) (modifySupply r f)+  where Node _ l r = s  -- (Supply, supplyValue, modifySupply) form a comonad: {-@@ -146,26 +142,31 @@ -}  --- Derived functions -----------------------------------------------------------+{-# SPECIALIZE newEnumSupply :: IO (Supply Int) #-}+-- | A supply of values that are in the 'Enum' class.+-- The initial value is @toEnum 0@, new values are generates with 'succ'.+newEnumSupply        :: (Enum a) => IO (Supply a)+newEnumSupply         = newSupply (toEnum 0) succ --- | Generate an infinite list of supplies by using 'supplyLeft' and--- 'supplyRight' repeatedly.-split          :: Supply a -> [Supply a]-split s         = supplyLeft s : split (supplyRight s)+{-# SPECIALIZE newNumSupply :: IO (Supply Int) #-}+-- | A supply of values that are in the 'Num' class.+-- The initial value is 0, new values are generated by adding 1.+newNumSupply         :: (Num a) => IO (Supply a)+newNumSupply          = newSupply 0 (1+) --- | Split a supply into two different supplies.--- The resulting supplies are different from the input supply.-split2         :: Supply a -> (Supply a, Supply a)-split2 s        = (supplyLeft s, supplyRight s)+{-# SPECIALIZE newDupableEnumSupply :: IO (Supply Int) #-}+-- | A supply of values that are in the 'Enum' class.+-- The initial value is @toEnum 0@, new values are generates with 'succ'.+-- WARNING: See comment on 'newDupableSupply'+newDupableEnumSupply :: (Enum a) => IO (Supply a)+newDupableEnumSupply  = newDupableSupply (toEnum 0) succ --- | Split a supply into three different supplies.-split3         :: Supply a -> (Supply a, Supply a, Supply a)-split3 s        = let s1 : s2 : s3 : _ = split s-                  in (s1,s2,s3)+{-# SPECIALIZE newDupableNumSupply :: IO (Supply Int) #-}+-- | A supply of values that are in the 'Num' class.+-- The initial value is 0, new values are generated by adding 1.+-- WARNING: See comment on 'newDupableSupply'+newDupableNumSupply  :: (Num a) => IO (Supply a)+newDupableNumSupply   = newDupableSupply 0 (1+) --- | Split a supply into four different supplies.-split4         :: Supply a -> (Supply a, Supply a, Supply a, Supply a)-split4 s        = let s1 : s2 : s3 : s4 : _ = split s-                  in (s1,s2,s3,s4)

value-supply.cabal view

@@ -1,9 +1,11 @@ Name:           value-supply-Version:        0.4+Version:        0.5+Homepage:       http://github.com/yav/value-supply License:        BSD3 License-file:   LICENSE Author:         Iavor S. Diatchki Maintainer:     iavor.diatchki@gmail.com+ Category:       Data Synopsis: A library for generating values without having to thread state. Description: