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'. -- Felipe.

This is implemented in Data.Supply (http://hackage.haskell.org/package/value-supply). The difference is: Data.Unique is *globally* unique, while Data.Supply is only locally unique. I ran into problems with this when writing tests. 2009/6/30 Ryan Ingram :

On Tue, Jun 30, 2009 at 9:16 AM, Felipe Lessa 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Push the envelope. Watch it bend.