unique identifiers as a separate library

[Isaac Dupree]

Iavor Diatchki wrote:
>   - It uses unsafeDupableInterleaveIO to avoid double locking,

in particular,

> gen r = unsafeDupableInterleaveIO
>               $ do v <- unsafeDupableInterleaveIO (genSym r)
>                    ls <- gen r
>                    rs <- gen r
>                    return (Node v ls rs)

where is the double locking?  We want referential 
transparency...

e.g. suppose you use newNumSupply to create a thunk for a 
Gen; when evaluated, it will run unsafeDupableInterleaveIO. 
  You send that thunk off to two different other threads. 
Then those threads decide to evaluate it (say, enough to get 
the first genSym'd value) and happen to make a race 
condition, so it becomes two separate IO computations. 
Therefore one of them runs atomicModifyIORef, and the other 
one runs atomicModifyIORef, and so they get two different 
values out.

Node 0 (...) (...)
Node 1 (...) (...)

when it's suppose to be the very same Gen data structure.

so, am I right or wrong about what the perils of 
unsafeDupableInterleaveIO are?

I could see changing (unsafe[Dupable]InterleaveIO (genSym 
r)) to (genSym r), to halve the number of 
unsafeInterleaveIOs needed if we assume that most of the 
time a node is evaluated in order to get a value... but it's 
hard to see a good way to make *fewer* InterleaveIOs than 
there are genSym'd values.  (possible, but hard, and really 
depends on the relative expenses/risks of locking, of 
computing the next number, and of using up the "address 
space" of all possible Ints for example).  Maybe the outer 
InterleaveIO could "strictly" make a few levels of Nodes 
(with lazy genSym'd values this time) before "interleaving" 
again, to reduce the amount of interleaving from the 
non-semantics-changing side.

-Isaac