On Tue, Jun 30, 2009 at 9:16 AM, Felipe Lessa<[email protected]> wrote: > On Tue, Jun 30, 2009 at 07:57:07PM +0530, Hemanth Kapila wrote: >> Can't we come up with something like this staying within the >> limits of purity? > > No, because that would break referential transparency :(. I.e., > it would be possible to distinguish things that should be > "equal", such as '3' from '1+2'.
This isn't entirely true; you can do something like this: > newtype Unique = U Integer deriving (Eq) > newtype UniqueM a = UniqueM (State Integer a) deriving Monad > runUniqueM (UniqueM a) = evalState a 0 > newUnique = UniqueM $ do > u <- get > put $! (u+1) > return (U u) Also, if you are willing to go inside of IO/ST for some bits of your code, you can use some tricks with unsafeInterleaveIO/ST to create data structures with unique ids that only get created if they are used; this allows creating infinite data structures and still keeping object ID. The returned data structure is still pure if the "U" constructor is hidden; all we can do is compare uniques for equality. You can relax this slightly by adding an Ord derivation; this technically allows you to observe creation order for the uniques which is wrong, but it's quite useful to be able to use Uniques as map keys. > data Tree a = Tree a (Tree a) (Tree a) > infTree :: IO (Tree Unique) > infTree = do > r <- newIORef 0 > mkTree r > mkTree :: IORef Integer -> IO (Tree Unique) > mkTree r = unsafeInterleaveIO $ do > v <- readIORef r > writeIORef r $! (v+1) > l <- mkTree r > r <- mkTree r > return (Tree (U v) l r) I believe GHC uses this technique internally. -- ryan _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
