Improving containers library

[Edward Kmett]

I've used it in a set of bottom-up applicative parser combinators, so that I
could make them provide an Applicative interface, but be warned, allocation
of a stable name involves a fair bit more than just doing a pointer
comparison. IIRC, Andy Gill has a paper on a related approach, which he uses
in his version of Lava.

Although I haven't benchmarked it, I have a strong suspicion that it is
likely cheaper to just unsafePerformIO to allocate a new IORef (), add that
as a member, and to check those for equality. Of course you then need to be
disciplined about not sharing the refs. This is the approach taken by the
mainstream Lava distribution.

Also, be warned that common subexpression elimination might yield more
positives than you would expect from a naive source reading.

-Edward Kmett

On Wed, Mar 3, 2010 at 1:59 PM, Milan Straka <fox at ucw.cz> wrote:

> Hi,
>
> thanks for enlightening me :) I wished for something like this some time
> ago...
>
> Milan
>
>
> > You should seq or use a bangpattern on the arguments before taking the
> > stable names to ensure that the result is reproducible if the input
> thunks
> > may later be forced.
> >
> > > let y = 1 + 1; x = id y in (ptrEqual x y, x `seq` y `seq` ptrEqual x y)
> > (False,True)
> >
> > a === b = a `seq` b `seq` unsafePerformIO $ (==) <$> makeStableName a <*>
> > makeStableName b
> >
> > > let y = 1 + 1; x = id y in (x === y, x `seq` y `seq` x === y)
> > (True,True)
> >
> > This may be less of a problem if your tree has bang patterns, but even
> there
> > it it sometimes easy to trip up and make a mistake with the unforced root
> of
> > a tree.
> >
> > -Edward Kmett
> >
> > On Wed, Mar 3, 2010 at 1:08 PM, Jonathan Cast <jonathanccast at fastmail.fm
> >wrote:
> >
> > > On Wed, 2010-03-03 at 18:58 +0100, Axel Simon wrote:
> > > > On 03.03.2010, at 17:30, Milan Straka wrote:
> > > >
> > > > > Any easy way of comparing pointers? I mean, if I have something
> like
> > > > > Tree a = N | B (Tree a) a (Tree a)
> > > > > and have (l::Tree a) and (r::Tree a), can I ask about the "physical
> > > > > equality"?
> > > >
> > > > You can! Despite the names appearing in the following code, the
> > > > following is safe:
> > > >
> > > > -- | Equality on pointers.
> > > > ptrEqual :: a -> a -> Bool
> > > > ptrEqual x y = unsafePerformIO $ do
> > > >    nx <- makeStableName x
> > > >    ny <- makeStableName y
> > > >    return (nx==ny)
> > >
> > > Safe but not pure?
> > >
> > > jcc
> > >
> > >
> > > _______________________________________________
> > > Libraries mailing list
> > > Libraries at haskell.org
> > > http://www.haskell.org/mailman/listinfo/libraries
> > >
>
> > _______________________________________________
> > Libraries mailing list
> > Libraries at haskell.org
> > http://www.haskell.org/mailman/listinfo/libraries
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20100303/f3eef070/attachment.html