[Haskell-cafe] Suggestions for simulating Object ID
ryani.spam at gmail.com
Tue Jun 30 12:44:36 EDT 2009
On Tue, Jun 30, 2009 at 9:16 AM, Felipe Lessa<felipe.lessa at gmail.com> 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.
More information about the Haskell-Cafe