On Tue, Jun 30, 2009 at 9:16 AM, Felipe Lessa
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