Good idea. GHC uses it http://darcs.haskell.org/ghc/compiler/basicTypes/UniqSupply.lhs
Lennart Augustsson and friends invented it @techreport{Augustsson92a, author = {L Augustsson and M Rittri and D Synek}, title = {Splitting infinite sets of unique names by hidden state changes}, type = {Report 67, Programming Methodology Group, Chalmers University}, month = may, year = {1992}, keywords = {name supply, monad plumbing, gensym, unique names} } Simon | -----Original Message----- | From: [EMAIL PROTECTED] [mailto:haskell-cafe- | [EMAIL PROTECTED] On Behalf Of C Rodrigues | Sent: 19 October 2007 15:16 | To: haskell-cafe@haskell.org | Subject: [Haskell-cafe] Hiding side effects in a data structure | | | While thinking about how to generate unique integer IDs on demand without | using a state variable, I came up with an interesting design pattern. It's a | way of doing side-effecting computation outside IO. Referential transparency | is preserved by making the side effects spatial rather than temporal: by | hiding side effects behind lazy thunks in a data structure, they can be | disguised as the output of a single, apparently nondeterministic IO function | used to data structure. This lets pure code use nondeterministic computation | without the monadic plumbing required to maintain state. | | The getContents function works this way, but I came up with a more | interesting example. The code below is a source of unique integer IDs that | is modeled after the RandomGen class. It uses unsafeInterleaveIO under the | hood, preserving referential transparency but not determinism. | | It seems to work. However, I'm not entirely sure how safe my use of | unsafeInterleaveIO is. In particular, could the two branches of the tree get | CSE'd? I'm also curious what people think about the general design pattern. | | module Unique where | | import Control.Monad(liftM) | import Data.IORef | import System.IO.Unsafe | | -- The goal is to produce an infinite tree of integers where each node in the | -- tree has a unique value. | type Unique = Int | data Supply = Supply Unique Supply Supply | | -- The tree can be used in a stateful manner as a source of unique integers. | getUnique :: Supply -> (Unique, Supply) | getUnique (Supply u s1 _) = (u, s1) | | -- The tree can also be split into independent sources of unique integers. | split :: Supply -> (Supply, Supply) | split (Supply _ s1 s2) = (s1, s2) | | -- The catch is, the tree will probably be visited very sparsely, with most | of | -- it being skipped. Assigning every node its own integer is very bad, | because | -- that will waste most of the 2^32 available integers very quickly. In | fact, | -- it can get used up in just 32 calls to getUnique. | -- | -- Instead, we'll create a tree where integers magically appear only in | places | -- where they are actually used. | | -- First, we need an IO-bound supply of integers. | newtype IOSupply = IOSupply (IORef Unique) | | newIOSupply :: IO IOSupply | newIOSupply = liftM IOSupply $ newIORef 0 | | getUniqueIO :: IOSupply -> IO Unique | getUniqueIO (IOSupply s) = do | u <- readIORef s | writeIORef s $ u+1 | return u | | -- Now we'll use the IO-bound supply to create a tree having the desired | -- properties. | {-# NOINLINE getPureSupply #-} | getPureSupply :: IOSupply -> IO Supply | getPureSupply s = do | s1 <- unsafeInterleaveIO $ getPureSupply s | s2 <- unsafeInterleaveIO $ getPureSupply s | n <- unsafeInterleaveIO $ getUniqueIO s | return $ Supply n s1 s2 | | _________________________________________________________________ | Climb to the top of the charts! Play Star Shuffle: the word scramble | challenge with star power. | http://club.live.com/star_shuffle.aspx?icid=starshuffle_wlmailtextlink_oct___ | ____________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe@haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe